Задача почтальона

Почтальон выходит из вершины P и должен вернутся в эту вершину
Каждый город проходит по одному разу всего 4 города расположенные
как параллелограм. Найти кратчайшее расстояние


Можно ли здесь воспользоваться жадным алгоритмом(выбор кратчайшего расстояния)

А чем простой перебор не катит. Перебираешь все упорядоченные комбинации из четырех вершин - 3! (6) вариантов.

препод сказал перебором не делать

А я вообще не понмаю. Какой параллелограм и какой путь? Не ясно. Путь от чего до чего. А параллелограме вообще все ребра ясны... В общем, пояснее можно?

жадным низя... тута надо динамическим программированием (что в этом случае почти полный перебор)

алгоритм пишут для общих задач что за прикол с четырьмя вершинами  ???


в принципе можно решить с помощью целочисленного програмирования

а вообще задача относиться к классу NP полных и сомнительна для пономиального решения


кто ее решит за полиномиальное время заработает много денег и убьет систему RSA

Tak eto zhe zada4a komivojadzhera!
Ni4ego lu46e polnogo (nu ladno, po4ti polnogo) perebora zdes' naiti slozhno  :(

Господа, не мудрите.
Типичная задачка на поиск кратчайшего пути в графах с весовыми ребрами.
Предлагаю сбегать посмотреть http://algolist.manual.ru/ ;D ;D ;D

4 вершины ..... извиняюсь, но мне даже смешно стало.
Да ведь реальзация либого, даже простейшего алгоритма поиска пути займет больше чем ручной перебор вариантов.
а задачи на поиск гамельтоновых циклов во взвешанных графах перебором и решаються, ну конечно с некоторой оптимизацией

поиск в ширину, поиск в глубину,  алгоритм дейкстры...
(типа ключевые слова)

Я сделал методом ветвей и границ (типа улучшенный перебор)
препод говорит у него есть алгоритм для N вершин, но даст его в конце семестра

Боюсь ошибиться, но мне кажется, что для любого паралеллогамма обход по сторонам будет оптимальным (в вырожденном случае - все обходы одинаковы).
Пытаюсь это доказать. Если не надоест возиться - выложу доказательство.

Таким образом, если моя гипотеза верна, результат тривиален. (Помнится, когда в школе на теме "Циклы" задали посчитать сумму чисел от 1 до N, я выводил результат: N*(N+1)/2 - вариант верный, хотя и не по теме)

Боже, какой же я идиот! Надо было сходить за хлебом два часа тому назад, а не залезать в тригонометрию и векторное исчисление!

Короче, доказательство:
Пусть ABCD - наш паралеллограмм, а O - точка пересечения диагоналей.
Докажем Лемму:

Цитата

Сумма длин диагоналей невырожденного выпуклого четырёхугольника всегда больше суммы длин двух несмежных сторон.
Действительно: рассмотрим треугольник AOB, по неравенству треугольника, |AO|+|OB|>|AB|.
Точно так же |CO|+|DB|>|CD|
Следовательно, |AC|+|BD|=|AO|+|OC|+|BO|+|OD|>|AB|+|CD|
аналогично и для сторон AD и BC. ч.т.д.

Из Леммы очевидно следует сабж, ибо вариантов обхода всего два - по четырём сторонам или по двум несмежным сторонам и двум диагоналям.

Таким образом задачу можно обобщить на любые выпуклые четырёхугольники (ибо мы не использовали свойства парелеллограмма, кроме его выпуклости)