Эвристика в графическом обращении

Question

Я пытаюсь использовать A *, чтобы найти оптимальный путь в графе.

Контекст заключается в том, что турист начинает свой отель, посещает достопримечательности и возвращается в свой отель в конце дня. Узлы (ориентиры) имеют два значения: важность и время. Края имеют два значения: затраченное время и стоимость (валюта).

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

Answer 1

У вас есть многомерная цель (стоимость и важность), и поэтому ваша проблема неуместна, потому что вы не определили, как соотносить стоимость и важность, когда вы «минимизируете» стоимость и «максимизируете» важность. Вы получите только частичный заказ на сайтах, чтобы показать, потому что некоторые пары сайтов могут быть несравнимыми, потому что один сайт может иметь более высокую стоимость и более высокую важность, в то время как другой может иметь более низкую стоимость и меньшее значение. Посмотрите на проблему с несколькими объективами, если вам нужны конкретные способы формализации и решения вашей проблемы. И будьте осторожны - это может стать немного волосатым, чем глубже вы пойдете в литературу.