用BFS验证金蛋1025部分最小循环 – 代码及其细节
|
18
|
0
|
数据结构及其算法

1721 字
|
8 分钟

这是一个关于验证互动视频《你被困在2025年10月25日》最短路径的方案。通过将视频中的人物和事件抽象为图结构，使用宽度优先搜索(BFS)算法找到了完成所有关键事件的最短路径。

读者应当充分探索了原视频。指路：【你被困在2025年10月25日（全新9个循环）】

源码放到文章最下方了，也可以通过洛谷云剪贴板获取。

声明：代码的实现部分使用了GitHub Copilot辅助。

B站视频演示

形式化问题

给定若干节点（人物）和有向边（事件），其中有向边包括从某一节点指向自身的。某些边要求此前走过特定的边才能走。目标是找到从起始节点到目标节点，并且触发过所有关键事件的最短路径。

思路

建模

将视频中的部分人物和事件抽象为有向图结构。

  • 每个人物可以触发特定的事件，而每个事件又可能影响其他人物或事件。人物和事件分别代表图的节点和边。
    • 原作的某些事件，对于寻找最短路径，很明显是无意义的循环事件，这些事件不计入图中。
  • 互动中的“学习机制”通过事件的约束关系表示，即某些事件具有它的前置事件。
  • 目标是找到最短路径，使所有关键事件都被触发。

构建出来的图暂时留空，需等待作者更新咕咕咕。

算法

使用宽度优先搜索（BFS）。从起始人物（Steve）开始，逐步探索所有可能的事件组合。

  • BFS保证了找到的路径是最短的，因为它按层次遍历图。
  • 在每一步中，检查当前事件是否满足所有关键事件的条件，并记录路径。
  • 由于编写此算法前已经有全流程30循环、28循环、26循环等的解答，目标的路径长度不会大于14，从而认为BFS的复杂度可以接受。

代码细节

由于代码编写较为仓促，存在一些冗余、复杂、缺少优化的地方，但在现有问题的复杂度下可以给出答案。

数据结构

使用结构体，表示事件和BFS队列中的事件列表。

  • Event结构体表示一个事件，包括起始人物、目标人物和事件ID
  • BFSEventList结构体表示BFS队列事件列表元素，包括当前事件、事件计数、前一个事件索引和关键事件标志。
  • EventList二维数组表示有向边，EventConstraint用于存储边的约束。
  • BFSQueue数组用于存储BFS队列中的事件列表。
  • finaleEventIndex用于记录找到的目标事件索引。

还包括一些宏定义来简化代码中的人物和事件标识。

  • Steve, Creeper, Diamond, Enderman, Villager, (Iron)Golem分别用0到5表示。
  • 事件用位掩码表示，例如CS1表示Creeper杀死Steve的事件。
    • 具体事件编码方式见文末“形象化问题描述”
  • ALL_EVENTS表示所有关键事件的组合。
  • MAXLEN定义了BFS队列的最大长度。

算法

  • CheckConstraintHappened()函数检查某个事件是否已经发生。
    • 通过回溯BFS队列，检查前面的事件是否满足约束条件。
  • isCriticalEvent()函数判断当前事件是否为关键事件。
  • BFS()函数实现了BFS算法，逐步探索所有可能的事件组合。

BFS详解

  • 初始化BFS队列，起始事件为Steve，没有前置事件，事件计数为1，关键事件标志为0b000000。
  • 使用两个指针front和rear来管理BFS队列。
  • 在每次循环中，取出当前事件（不清除元素），遍历所有可能的下一个事件。
  • 对于每个可能的下一个事件，通过回溯前面的事件，检查是否满足约束条件。
  • 如果满足条件，创建新的BFSEventList元素，更新事件计数和关键事件标志，并将其加入BFS队列。
  • 检查是否达到了目标状态（Steve且所有关键事件都发生），如果是则记录索引并返回。
  • 如果队列长度超过MAXLEN，则停止搜索。
void BFS()
{
    int front = 0, rear = 0;
    BFSQueue[rear++] = {{-1, Steve, 0}, 1, -1, 0};

    while (front < rear)
    {
        BFSEventList current = BFSQueue[front++];
        for (char i = 0; i < 6; i++)
        {
            for (char j = 0; j < 3; j++)
            {
                if (EventList[current.currentEvent.to][i][j] == true)
                {
                    Event constraint = EventConstraint[current.currentEvent.to][i][j];
                    if (constraint.from != -1)
                    {
                        if (!CheckConstraintHappened(constraint, front - 1))
                            continue;
                    }

                    BFSEventList next;
                    next.currentEvent = {current.currentEvent.to, i, j};
                    next.eventCount = current.eventCount + 1;
                    next.previousEventIndex = front - 1;

                    // check critical event and character
                    next.CriticalEvent = current.CriticalEvent | isCriticalEvent(next.currentEvent);
                    BFSQueue[rear++] = next;
                    if (rear >= MAXLEN)
                        break;

                    // check target achieved
                    if (i == Steve && next.CriticalEvent == ALL_EVENTS)
                    {
                        finaleEventIndex = rear - 1;
                        return;
                    }
                }
            }
        }
        if (rear > MAXLEN)
            break;
    }
    cout << rear << endl;
    cout << BFSQueue[MAXLEN].eventCount << endl;
}

主函数逻辑

  • InitEventList()函数初始化事件列表，定义了每个人物可以触发的事件。
  • InitEventConstraint()函数初始化事件约束，定义了每个事件的前置条件。
  • BFS()函数执行BFS搜索。
  • CheckResult()函数检查BFS结果，回溯路径并输出事件序列。

输出结果

经过两轮调试，最终输出了最短路径长度和事件序列：

14
(SS)
(SC)
(CS)
(SD)
(DS)
(SE)
(ES)
(SV)
(VV)
(VD)
(DS)
(SE)
(EG)
(GS)
// 事件序列的含义见文末“形象化问题描述”

BFS过程中，实际使用的队列长度超过了 10^6，幸运的是在 10^7 范围内程序求解出了其中一个解。

你能想象吗？在原视频中，最短路径长度为14，BFS搜索过程模拟了百万级别的世界线。

后记

算法实际上有多种优化空间，例如：

  • 进一步压缩事件的状态表示
  • 特判某些原地循环事件并跳过（史蒂夫每天被苦力怕炸，村民每天给铁傀儡涨工资，……）
  • ……

时隔多年后再次编写BFS相关代码，感触颇深。BFS作为一种基础的图搜索算法，解决这个现实问题依然有效。

附：完整代码与形象的问题描述

/*
1025 BFS Solution of 5 Events & Enderman's Slack-off & Returning to Cycle 1(Steve)
Author: Lylighte
Assisted by GitHub Copilot
*/
#include <bits\stdc++.h>
using namespace std;

#define Steve 0
#define Creeper 1
#define Diamond 2
#define Enderman 3
#define Villager 4
#define Golem 5

#define CS1 1<<0
#define DS2 1<<1
#define ES1 1<<2
#define EG  1<<3
#define VD1 1<<4
#define GS1 1<<5
#define ALL_EVENTS (CS1|DS2|ES1|EG|VD1|GS1)

#define MAXLEN 10000000

struct Event
{
    char from;
    char to;
    char eventID;
};

struct BFSEventList
{
    Event currentEvent;
    int eventCount;
    int previousEventIndex;
    char CriticalEvent;
};

bool EventList[6][6][3];

Event EventConstraint[6][6][3];

BFSEventList BFSQueue[MAXLEN+10];

int finaleEventIndex = -1;

void InitEventList()
{
    // Steve Events
    EventList[Steve][Steve][0] = '1';
    EventList[Steve][Creeper][0] = '1';
    EventList[Steve][Enderman][0] = '1';
    EventList[Steve][Diamond][0] = '1';
    EventList[Steve][Golem][1] = '1';
    EventList[Steve][Villager][0] = '1';

    // Creeper Events
    EventList[Creeper][Steve][1] = '1';
    EventList[Creeper][Villager][0] = '1';

    // Diamond Events
    EventList[Diamond][Villager][0] = '1';
    EventList[Diamond][Steve][1] = '1';
    EventList[Diamond][Steve][2] = '1';

    // Enderman Events
    EventList[Enderman][Diamond][0] = '1';
    EventList[Enderman][Steve][0] = '1';
    EventList[Enderman][Steve][1] = '1';
    EventList[Enderman][Golem][0] = '1';

    // Villager Events
    EventList[Villager][Villager][0] = '1';
    EventList[Villager][Golem][1] = '1';
    EventList[Villager][Diamond][1] = '1';

    // Golem Events
    EventList[Golem][Villager][1] = '1';
    EventList[Golem][Steve][0] = '1';
    EventList[Golem][Steve][1] = '1';
}

void InitEventConstraint()
{
    memset(EventConstraint, 0xff, sizeof(EventConstraint));
    // Steve Events
    EventConstraint[Steve][Golem][1] = {Villager, Villager, 0};

    // Creeper Events
    EventConstraint[Creeper][Steve][1] = {Steve, Steve, 0};

    // Diamond Events
    EventConstraint[Diamond][Steve][1] = {Steve, Steve, 0};
    EventConstraint[Diamond][Steve][2] = {Steve, Diamond, 0};

    // Enderman Events
    EventConstraint[Enderman][Steve][1] = {Steve, Diamond, 0};

    // Villager Events
    EventConstraint[Villager][Golem][1] = {Villager, Villager, 0};
    EventConstraint[Villager][Diamond][1] = {Steve, Enderman, 0};

    // Golem Events
    EventConstraint[Golem][Villager][1] = {Villager, Villager, 0};
    EventConstraint[Golem][Steve][1] = {Villager, Villager, 0};
}

bool CheckConstraintHappened(const Event &constraint, const int position)
{
    int idx = position;
    while (idx != -1)
    {
        BFSEventList event = BFSQueue[idx];
        if (event.currentEvent.from == constraint.from &&
            event.currentEvent.to == constraint.to &&
            event.currentEvent.eventID == constraint.eventID)
        {
            return true;
        }
        idx = event.previousEventIndex;
    }
    return false;
}

char isCriticalEvent(const Event &event)
{
    if (event.from == Creeper && event.to == Steve && event.eventID == 1)
        return CS1;
    if (event.from == Diamond && event.to == Steve && event.eventID == 2)
        return DS2;
    if (event.from == Enderman && event.to == Steve && event.eventID == 1)
        return ES1;
    if (event.from == Enderman && event.to == Golem && event.eventID == 0)
        return EG;
    if (event.from == Villager && event.to == Diamond && event.eventID == 1)
        return VD1;
    if (event.from == Golem && event.to == Steve && event.eventID == 1)
        return GS1;
    return 0;
}

void BFS()
{
    int front = 0, rear = 0;
    BFSQueue[rear++] = {{-1, Steve, 0}, 1, -1, 0};

    while (front < rear)
    {
        BFSEventList current = BFSQueue[front++];
        for (char i = 0; i < 6; i++)
        {
            for (char j = 0; j < 3; j++)
            {
                if (EventList[current.currentEvent.to][i][j] == true)
                {
                    Event constraint = EventConstraint[current.currentEvent.to][i][j];
                    if (constraint.from != -1)
                    {
                        if (!CheckConstraintHappened(constraint, front - 1))
                            continue;
                    }

                    BFSEventList next;
                    next.currentEvent = {current.currentEvent.to, i, j};
                    next.eventCount = current.eventCount + 1;
                    next.previousEventIndex = front - 1;

                    // check critical event and character
                    next.CriticalEvent = current.CriticalEvent | isCriticalEvent(next.currentEvent);
                    BFSQueue[rear++] = next;
                    if (rear >= MAXLEN)
                        break;

                    // check target achieved
                    if (i == Steve && next.CriticalEvent == ALL_EVENTS)
                    {
                        finaleEventIndex = rear - 1;
                        return;
                    }
                }
            }
        }
        if (rear > MAXLEN)
            break;
    }
    cout << rear << endl;
    cout << BFSQueue[MAXLEN].eventCount << endl;
}

void CheckResult()
{
    if (finaleEventIndex == -1)
    {
        cout << "Impossible" << endl;
        return;
    }
    vector
<Event> resultEvents;
    int idx = finaleEventIndex;
    while (idx != -1)
    {
        BFSEventList event = BFSQueue[idx];
        resultEvents.push_back(event.currentEvent);
        idx = event.previousEventIndex;
    }
    reverse(resultEvents.begin(), resultEvents.end());
    cout << resultEvents.size() - 1 << endl;
    for (size_t i = 1; i < resultEvents.size(); i++)
    {
        Event event = resultEvents[i];
        char fromChar, toChar;
        switch (event.from)
        {
        case Steve:
            fromChar = 'S';
            break;
        case Creeper:
            fromChar = 'C';
            break;
        case Diamond:
            fromChar = 'D';
            break;
        case Enderman:
            fromChar = 'E';
            break;
        case Villager:
            fromChar = 'V';
            break;
        case Golem:
            fromChar = 'G';
            break;
        }
        switch (event.to)
        {
        case Steve:
            toChar = 'S';
            break;
        case Creeper:
            toChar = 'C';
            break;
        case Diamond:
            toChar = 'D';
            break;
        case Enderman:
            toChar = 'E';
            break;
        case Villager:
            toChar = 'V';
            break;
        case Golem:
            toChar = 'G';
            break;
        }
        cout << "(" << fromChar << toChar;
        if (event.eventID > 0)
            cout << event.eventID;
        cout << ")" << endl;
    }
}

int main()
{
    InitEventList();
    InitEventConstraint();
    BFS();
    CheckResult();
    return 0;
}

Result:

14
(SS)
(SC)
(CS)
(SD)
(DS)
(SE)
(ES)
(SV)
(VV)
(VD)
(DS)
(SE)
(EG)
(GS)

Figurative problem description

Characters:

Steve, Creeper, Diamond, Enderman, Villager, Golem

Events:

Events are coded like (ABx), where A is the initiator character, B is the target character, and x is the event ID (if multiple events exist between the same characters). Omit x if x=0. Event whose x is 1 or 2 has constraint.

Useful Relationships:

Steve

  • (SS)Killed by Creeper -> Steve
  • (SC)Fight using wood sword -> Creeper
  • (SE)Successful Trade -> Enderman
  • (SD)Make a diamond sword -> Diamond
  • (SG1)Send Flowers -> Golem
    • (VV) needed
  • (SV)Kill the villager -> Villager

Creeper

  • (CS1)Kill Steve in the cave -> Steve
    • (SS) needed
  • (CV)Kill Villager -> Villager

Diamond

  • (DV)Witness Villager’s Death -> Villager
  • (DS1)Witness Steve’s Death -> Steve
    • (SS) needed
  • (DS2)Turn into a sword -> Steve
    • (SD) needed

Enderman

  • (ED)Steal the Diamond -> Diamond
  • (ES0)Kill Steve outside -> Steve
  • (ES1)Kill Steve in stronghold -> Steve
    • (SD) needed
  • (EG)Slack off in village -> Golem

Villager

  • (VV)Pay Golem -> Villager
  • (VG1)Protected by Golem -> Golem
    • (VV)needed
  • (VD1)Make a deal with Steve -> Diamond
    • (SE) needed

Golem

  • (GV1)Paid by Villager -> Villager
    • (VV) needed
  • (GS0)Killed Steve -> Steve
  • (GS1)Protect Villager -> Steve
    • (VV) needed

Target Status:

Charater – Steve Triggered Events – (CS1), (DS2), (ES1), (EG), (VD1), (GS1)

Start At:

Steve, No Events

上一篇