Эвристический алгоритм A *

У меня проблема с A *, но мне сложно создать хорошую эвристику.Эвристический алгоритм A *

Моя проблема являются:

Определить оптимальный маршрут для достижения грузовиком сбора мусора в городе, который перемещается по карте, известной стремится максимизировать нагрузку и уменьшить время в пути.

У меня есть 4 типа узлов: Geral Nodes, Dump Nodes, Garbage Nodes и Gas Nodes.

У грузовика для мусора может закончиться газ и есть возможность пополнить автомобиль. Там также может быть более 1 мусорной корзины, куда доставлять.

Какова наилучшая эвристика для решения этой проблемы?

С уважением

источник

2013-04-14 mistic

Хороший первый проход поиска эвристика использовать жадный алгоритм. Например, в общем алгоритме маршрутизации (найти кратчайший маршрут между городами) достойная эвристика - использовать жадный алгоритм, в котором вы всегда направляетесь в ближайший город, ближайший к месту назначения, как ворона; это эвристика с линейным временем и никогда не переоценивает решение. В вашем случае, возможно, вы можете использовать жадный алгоритм, в котором мусоровоз всегда идет к ближайшему ближайшему мусорному узлу или мусорному узлу с самым мусором; Я не могу быть более конкретным, не зная деталей четырех узлов, которые вы используете, но вы получаете идею. Любой алгоритм с линейным временем, который не переоценивает решение, будет делать, и вы сможете настроить его на следующем проходе. (В большинстве случаев приемлема эвристика nlog (n), n^2 становится ужасно дорогой.)

источник

2013-04-14 23:33:43

Узел уплотнения, узел мусора и газовый узел являются подклассами Geral Node. У узла Geral только имя, x и y позиция и уникальный идентификатор и идентификатор типа узла. Дамп-узел и газовый узел отличаются только от geral node на тип узла. У узлов мусора есть также переменная мусора, указывающая мусор, который имеет мусор ... Для этой проблемы я использую jgrapht и использую WeithedGraph этой библиотеки. У меня также есть класс под названием truck, который сохраняет maxCapacity, maxGAs и actualGas и actualCapacity грузовика .. Любая другая идея сделать это – mistic

Я предполагаю, что вам нужно посетить Дамп-узел, когда ваш грузовик заполнен, и вам нужно посетить газовый узел, прежде чем вы исчерпаете газ. Один жадный подход - посетить ближайший узел мусора, пока ваш трюк не будет заполнен (или следующий узел мусора с самым мусором или что-то еще), а затем сделайте beeline для Dump Node; если ваш грузовик исчерпал газ, перейдите в газовый узел. Это, вероятно, будет эвристическим дерьмом; следующий шаг - загрузить каждый узел мусора в соответствии с его близостью к Дамп-узлу, чтобы вы могли посетить узел Garbage Node, ближайший к дамп-узлу, прежде чем вы заходите в Dump Node. –

В какой-то момент вы, вероятно, захотите погрузить узлы мусора в соответствии с тем, насколько они близки к газовому узлу, так что вы заходите в узел мусора, ближайший к газовому узлу, перед заполнением. И так далее.Вы будете бесконечно настраивать эту вещь, пока не удовлетворитесь ею. Правила, которым вы должны следовать, - это: эвристика не может переоценить решение (которое будет не так долго, пока вы используете жадный алгоритм), и это должно быть O (n) или O (nlog (n)) (что будет, если вы основываете его на жадном алгоритме) –

A * отлично подходит для поиска самого быстрого/кратчайшего маршрута между 2 точками.

Однако ваша проблема с мусоровозом, вероятно, представляет собой совершенно иную проблему: вам нужно найти самый быстрый/короткий маршрут, заказав набор точек. Это проблема Traveling Salesman (TSP), или большой брат - проблема маршрутизации транспортных средств (VRP), оба из которых - NP-complete.

A * не может справиться с NP-полных задач, вам нужно алгоритмы, как метаэвристики и т.д. Ищите решения по проблемам TSP и ВРП, например the TSP and VRP example in OptaPlanner (java, open source) (который показан в this video).

источник

2013-04-17 09:52:22

На самом деле спасибо за ваш ответ. Я делаю эту работу для класса моего мастера в области информатики и в задании, что профессор хочет, чтобы эта проблема была решена с помощью A * ... До сих пор я не могу решить эту проблему с помощью g (x) и h (x), которые я выбираю. Мне нужно больше вариантов и предложений. – mistic

ответ

Смежные вопросы