#graph-theory
Вопрос:
Я хочу найти алгоритм для расчета количества сообщений, сгенерированных во время наводнения.
Эта фотография-вопрос, который я нашел в Интернете, и это то, что я хочу решить. Я думаю, что, возможно, модифицированный алгоритм Дейкстры может это сделать, но я не знаю, как. Более того, является ли этот вопрос своего рода типичной проблемой в теории графов? Если да, то как называется этот тип вопросов?
Ответ №1:
Если вы предполагаете, что узел перешлет сообщение всем соседним узлам, за исключением тех, которые находились на пути к полученному сообщению, и отбросит сообщения, которые он уже видел, то эти сообщения будут отправлены/получены:
| Время | Текущий Узел | Путь к Сообщению | Отправлено На | Причитается по | Примечания |
|---|---|---|---|---|---|
| 0 | X | X | V | 3 | |
| 0 | X | X | W | 6 | |
| 0 | X | X | Y | 6 | |
| 3 | V | XV | T | 7 | |
| 3 | V | XV | U | 6 | |
| 3 | V | XV | W | 7 | |
| 3 | V | XV | Y | 4 | |
| 4 | Y | XV | T | 11 | |
| 4 | Y | XV | Z | 16 | |
| 6 | U | XVU | S | 10 | |
| 6 | U | XVU | T | 8 | |
| 6 | U | XVU | W | 9 | |
| 6 | W | XW | V | 10 | |
| 6 | W | XW | U | 9 | |
| 6 | Y | XY | — | — | Отброшено, как уже было видно |
| 7 | T | XVT | S | 8 | |
| 7 | T | XVT | U | 9 | |
| 7 | T | XVT | Y | 14 | |
| 7 | T | XVT | Z | 12 | |
| 7 | W | XVW | — | — | Отброшено, как уже было видно |
| 8 | S | XVTS | Достигнута цель | ||
| 8 | T | XVUT | — | — | Отброшено, как уже было видно |
| 9 | U | XWU | — | — | Отброшено, как уже было видно |
| 9 | U | XVTU | — | — | Отброшено, как уже было видно |
| 9 | W | XVUW | — | — | Отброшено, как уже было видно |
| 10 | S | XVUS | — | — | Отброшено, как уже было видно |
| 10 | V | XWV | — | — | Отброшено, как уже было видно |
| 11 | T | XVYT | — | — | Отброшено, как уже было видно |
| 12 | Z | XVTZ | Y | 24 | |
| 14 | Y | XVTY | — | — | Отброшено, как уже было видно |
| 16 | Z | XVYZ | — | — | Отброшено, как уже было видно |
| 24 | Y | XVTZY | — | — | Отброшено, как уже было видно |
Таким образом, в общей сложности было отправлено 19 сообщений. Сообщение принимается S в момент времени = 8, а последнее сообщение принимается сетью в момент времени = 24.
Что касается алгоритма, когда узел отправляет сообщение:
- Он проверяет, не получал ли он сообщение раньше; и
- Если это не так, адресует копию сообщения каждому из соседних узлов, которые не являются предыдущими получателями сообщения;
- Затем передает эти сообщения «почтальону», который должен быть доставлен в текущее время плюс временная задержка на краю;
- Когда «почтальон» доходит до времени, когда должно быть отправлено сообщение, он доставляет его адресату, и алгоритм повторяется для каждого узла, получившего сообщение.