Модифицированный коммивояжер

Учитывая структуру графа с асимметричными затратами на ребрах, есть ли способ пройти определенный набор узлов с наименьшими затратами, если вы можете посетить каждый узел только один раз? Задача формулируется так, что такой путь должен существовать.


graph-algorithm traveling-salesman
person amatsukawa    schedule 13.11.2011    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Грубая сила в конце концов решит проблему.

person Casey Robinson    schedule 13.11.2011

arrow_upward
0
arrow_downward

Я бы использовал алгоритм A*.

person kol    schedule 13.11.2011
comment
Я попробовал использовать алгоритм USC, но он оказался почти эквивалентен BFS (великие граничные издержки). У меня нет хорошего предположения о допустимой эвристике. Существуют ли какие-либо неоптимальные решения, которые находят «довольно хорошее» решение? - person amatsukawa; 14.11.2011
comment
Нулевая эвристика допустима :) USC = ? - person kol; 14.11.2011
comment
USC = поиск по единой стоимости. A* вырождается в USC с нулевой эвристикой. - person amatsukawa; 14.11.2011
comment
Почему бы вам не использовать УСК? Вы хотите что-то более эффективное? - person kol; 14.11.2011
comment
Да, USC медленнее, чем жадный алгоритм перебора. Я просто думал, что есть что-то более эффективное. - person amatsukawa; 14.11.2011