Неориентированные графы

Question

У меня есть задание, которое я пытаюсь выполнить с помощью Java, но я не совсем понимаю, как настроить / каковы узлы для следующего графика.По сути, это проблема с перьевым плоттером, или более известная как проблема коммивояжера.Где мой следующий ввод:

Line between 4 1 and 4 4    
Line between 4 4 and 4 7    
Line between 2 6 and 4 4   
Line between 4 4 and 6 2  
Line between 6 6 and 4 4   
Line between 2 2 and 4 4   

, и мой вывод выглядит как:

<n> nodes explored
cost = 24.61
Move from 0 0 to 2 2
Draw from 2 2 to 4 4
Draw from 4 4 to 6 6
Move from 6 6 to 4 7
Draw from 4 7 to 4 4
Draw from 4 4 to 4 1
Move from 4 1 to 6 2
Draw from 6 2 to 4 4
Draw from 4 4 to 2 6

Предполагая, что вашим началом будет левый нижний угол листа бумаги (0, 0) и он идет вверх по координатам, каждая из которых является координатой узла, и как бы я определил, когда двигаться и рисовать линию.Я знаю, что должен использовать неориентированный граф с A *, но я все еще не совсем понимаю, какие из них являются узлами (вершинами) и как я могу определить, когда двигаться и когда рисовать линии, кто-нибудь может дать мне какой-нибудь совет?

РЕДАКТИРОВАТЬ: обратите внимание, что относится к количеству / количеству узлов, исследованных в течение всего поиска.

Answer 1

Чтобы использовать A *, вам сначала потребуется допустимая эвристическая функция .[объяснение того, что это в конце этого ответа].

Задача в виде графика для A: *
определить G = (V, E) как ваш график,так что:
V={all possible drawings prefixes} [т.е. все возможные «снимки» каждого возможного розыгрыша].обратите внимание, что вы не должны хранить этот график в памяти, но создайте его на лету с next(), что будет объяснено позже.[обратите внимание, что практически для каждого состояния вам нужно хранить только (1) где находится ручка в данный момент (2) какие линии уже нарисованы]
E={all possible changes from one 'snap shot' to another}
Вам также необходимо w:E->R [функция веса] это будет просто: w(point1,point2)=euclidian_distance(point1,point2)

Вы также должны определить next:V->P(V): next(v)={all snap shots you can get from v, using exactly one move/draw
Наконец, вы также должны определить F: все "конечные" состояния.F={all the prefixes which all the lines are drawn}

Как запустить A *:
начать со снимка, где ваше перо находится в точке (0,0), и линии не нарисованы [это начальное состояние] и продолжайте, пока не найдете одно из последних состояний.если да, если ваша эвристика верна, вы гарантированно получите оптимизированное решение, потому что A * является допустимым и оптимизированным

(*) допустимой эвристической функцией:
let h*(v)=real distance to target из вершины v.
эвристическая функция h: V-> R допустима, если h(v)<=h*(v) для каждого v в V

Ваш реальный вызов
Трудная часть для TSP находит допустимое значение h.Это так сложно, потому что вы понятия не имеете, что такое кратчайший путь, и если эвристическая функция недопустима, то не гарантируется, что найденное решение будет оптимизировано.

Предложение:
Возможно, вы захотите использовать какой-нибудь алгоритм в любое время . Когда я сделал нечто подобное, [решил TSP с несколькими агентами], я также использовал A *, но начал с недопустимой эвристики, и итеративноуменьшил его, поэтому, если у меня было достаточно времени, я нашел оптимальное решение, а если нет - вернул лучшее решение, которое смог найти.

Answer 2

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

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

Когда вы должны рисовать:
Ничья может произойти в двух ситуациях.После того, как вы перейдете к определенной точке, будет проведена ничья.Рисование также происходит, когда ваша Конечная точка сегмента линии присутствует в ArrayList в качестве начальной точки.

После каждого рисования вы должны удалить этот конкретный сегмент линии из ArrayList.Вы остановите свою программу, когда в вашем ведре ничего не останется.