многоуровневое отображение плана этажа

Question

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

В настоящий момент каждый этаж моделируется на графике следующим образом: дверь каждой комнаты является вершиной.соединения ребер, соединяющих комнаты с основным ребром (коридором), также являются вершинами.Лестница между этажами - ребра.

Остается вопрос, как мне представить лифты (лифты) (которые находятся рядом с лестницей)?Наличие этого ребра заставляет меня задуматься о том, какой вес он должен иметь, учитывая, что мне нужно будет запустить алгоритм обхода графа для нахождения кратчайшего пути.

Лифт (лифт) как край или как вершина?Вот в чем вопрос.спасибо!

Answer 1

Края

Использование края - самый быстрый ответ, как вы делаете это для лестниц.Однако в то время как лестница может подниматься только с этажа X на этаж X + 1, лифт может подниматься с любого этажа на любой этаж с немного отличающимся временем - обычно я нахожу лестницу быстрее на два этажа, но медленнее на более чем 2.отразите это вам понадобится ребро от каждого этажа до каждого второго этажа , с весами для каждого.

Вершины

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

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

---

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

Answer 2

Я голосую за край.

Скажем, вы решили использовать лифт. Вы идете к нему, нажимаете кнопку и ждете немного. Затем вы входите, ждете еще, выходите и продолжаете свой путь. Теперь, хотя вы физически не много двигаетесь, со временем вы двигаетесь. Подниматься на лифте между этажами - это все равно, что идти пешком, скажем, 50 метров.

То, что я имею в виду, это то, что время, проведенное стоя вокруг лифта, эквивалентно расстоянию, которое вы преодолеваете, идя Поэтому относитесь к лифту как к краю, по которому вы идете во время его использования. Используйте это расстояние, чтобы сравнить, скажем, спуск по лестнице.

Answer 3

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