Задача коммивояжера, Как реализовать с использованием стека? Опции

[LOVE133]

Все нужные темы закрыты, а новую создавать -мусорить понапрасну.Пишу здесь.Все таже задача коммивояжера, метод ветвей и границ.Но етсь одно но - использование стека.Как и куда его можно там запихнуть?

М

Лучше всегда открывать новую тему - мусор, если что, уберут. П.6: "одна тема - один вопрос"

Сообщение отредактировано: Michael_Rybak - 3.10.2007 19:41

[Michael_Rybak]

Обычная реализация - рекурсивная: начинаем в какой-то точке, отмечаем, что мы в ней были, выбираем куда идти и рекурсивно делаем то же самое. Тебе нужно сделать это же, но заменив рекурсию итерациями - как раз с помощью стека.

В стек помещаешь вершины в порядке обхода. Когда идти дальше некуда, достаешь из стека предыдущую вершину и продолжаешь перебор от нее; если для нее тоже кончились варианты - опять достаешь из стека; когда стек окажется пуст - перебор окончен.