如何编写找到最佳事件分布的算法？
How to write an algorithm which finds the best possible event distribution?
我正在尝试编写一种算法，该算法采用一系列事件（在本例中为电影放映 - 每部电影通常有不止一次放映，尽管情况并非总是如此）和 returns事件的最佳可能组合，即牺牲最少电影数量的事件。
我想出了这个我手动应用的算法，但我试图将其转换为代码并遇到了一些麻烦。我所做的（手动）是逐个筛选，检查它是否与任何其他筛选有冲突。如果是这样，它将通过选择两部冲突电影中的一部*（电影 A），删除电影 A 的所有其他放映，并删除电影B的那个放映。之后，它会寻找另一个电影B的放映，检查是否有冲突，然后重复这个过程。
* 通常是我当前正在检查的那个，但某些标准可能会影响决定，例如如果两部相互冲突的电影中有一部在其他地方免费（无冲突）放映，我只会选择那部并以这种方式解决冲突。反之，如果两部电影中有一部没有其他放映，我会选择那部。
最终这个“分支”最终会进行免费（无冲突）放映，这意味着整个分支都已解决（即可以在不牺牲任何其他电影的情况下观看所有涉及的电影），或者它会陷入僵局，这意味着这些决定的组合并没有带来完美的解决方案。在这种情况下，人们会回到递归的一个层次（即回到一个决定）并尝试选择另一个筛选。如果这不起作用，请返回另一个级别并重试。如果该分支中没有导致解决分支的决定组合，则必须由人类做出决定以牺牲导致问题的电影之一。
这几乎就是我要编写的代码，我以一种非常意识流的方式写了一个尝试，只是想尽快把它弄出来，因为我很兴奋，没有想得太远，只是解决问题。它适用于我正在尝试的电影节，它有点小（同时不超过 4 次放映），但是当我在更大的电影节上尝试它时崩溃（有时同时放映 6 次以上）。它超过了最大堆栈大小，可能是因为代码中的问题，尽管我不确定它是否只是 运行 正确并且只是进入那些递归级别。关于这一点，不确定使用 while 循环而不是递归是否可以更好地解决这个问题。
昨天我决定放弃我写的算法并以更好的计划方式从头开始，发现我认为展望未来的主要 2 个问题是：
- 当分支失败时算法“返回”并切换其先前决策的能力。这是该算法的核心机制，但我正在努力想出一种对其进行编码的好方法。在我之前的一个中，我实现了一个“检查点”系统，如果一个分支失败，它会恢复到最后一个检查点并从那里继续，如果它成功，它会把那个标记为新的检查点。但这只适用于顶层，不适用于“内部”决策。
- 事实上，大多数日程表都有不止一种解决方案。如果解决方案是完美的（即没有牺牲任何电影），那么问题就很小，无论哪种方式你都不会错过任何电影，最多你将被剥夺在同一部电影的几场放映之间进行选择的权利。但如果没有完美的解决方案，现在的选择可能是在你真正想看的 2 部电影和你不太关心的 2 部电影之间做出选择。这意味着该算法需要遍历每个可能的筛选组合以找到最佳组合，如果没有完美的解决方案，它会向您展示不同的可能性。但这将是暴力强制问题（除非绝对必要）并不是我正在寻找的问题。
对于此事的任何帮助或指导，我将不胜感激。作为参考，我正在用 Typescript + React + Next.js 写这篇文章，但我认为这是一个更一般的 CS 问题，所以再次感谢任何帮助。
当前的算法和模拟数据可以在这里找到：https://jsfiddle.net/procz/82n3jxLb/
const findBestSchedule = (
screeningData: IScreening[],
movies: IMovie[]
): IScreening[] => {
const debugLog = (type: string, args) => {
if (!DEBUG_LOG) return;
if (type === "process") {
return console.log(
`processing ${findMovie(
movies,
args.screening
).name.toUpperCase()} ${args.screening.date.getDate()} ${args.screening.date.getHours()}hs - called from ${
args.calledFrom
}, currentArray:`,
args.screenings
);
}
if (type === "conflict") {
return console.log(
`conflict between ${findMovie(
args.movies,
args.screening1
).name.toUpperCase()} ${args.screening1.date.getDate()} ${args.screening1.date.getHours()}hs and ${findMovie(
movies,
args.screening2
).name.toUpperCase()} ${args.screening2.date.getDate()} ${args.screening2.date.getHours()}hs`
);
}
if (type === "free") {
return console.log(
`${findMovie(
args.movies,
args.screening
).name.toUpperCase()} ${args.screening.date.getDate()} ${args.screening.date.getHours()}hs is free, deleting all other ${findMovie(
args.movies,
args.screening
).name.toUpperCase()}`
);
}
if (type === "recursion") {
return console.log(args.recursionLevel, args.array);
}
if (type === "unsolvable") {
return console.log(
`unsolvable conflict between ${findMovie(
args.movies,
args.screening1
).name.toUpperCase()} and ${findMovie(
args.movies,
args.screening2
).name.toUpperCase()}, backtracking`
);
}
if (type === "decision") {
return console.log(
`recursion level: ${args.recursionLevel} - choosing ${findMovie(
args.movies,
args.screening1
).name.toUpperCase()} ${args.screening1.date.getDate()} ${args.screening1.date.getHours()}hs, deleting ${findMovie(
args.movies,
args.screening2
).name.toUpperCase()} ${args.screening2.date.getDate()} ${args.screening2.date.getHours()}hs, deleting all other ${findMovie(
args.movies,
args.screening1
).name.toUpperCase()}`
);
}
if (type === "noConflict") {
return console.log(
`no conflicts found for ${findMovie(
args.movies,
args.screening
).name.toUpperCase()} ${args.screening.date.getDate()} ${args.screening.date.getHours()}hs, deleting all other ${findMovie(
args.movies,
args.screening
).name.toUpperCase()}`
);
}
};
const sortedScreenings = [...screeningData].sort(
(a, b) => b.date.getTime() - a.date.getTime()
);
let latestScreeningArray = sortedScreenings;
let recursionLevel = 0;
let lastSafeArray = latestScreeningArray;
let lastSafeRecursionLevel = recursionLevel;
const processScreening = (
screenings: IScreening[],
screening: IScreening,
calledFrom ? : string
): boolean => {
debugLog("process", {
screening,
calledFrom,
screenings
});
const findConflictingScreenings = (
screenings: IScreening[],
screening: IScreening
): IScreening[] => {
if (!screenings) return [];
return [...screenings].filter(
(otherScreening) =>
screening.id !== otherScreening ? .id &&
screeningsOverlap(screening, otherScreening, movies)
);
};
const conflictingScreenings = findConflictingScreenings(
screenings,
screening
);
if (conflictingScreenings.length) {
const resolveConflict = (
screening: IScreening,
otherScreening: IScreening
): boolean => {
debugLog("conflict", {
screening1: screening,
screening2: otherScreening,
movies,
});
const findNextScreenings = (
screenings: IScreening[],
screening: IScreening
): IScreening[] => {
return [...screenings]
.reverse()
.filter(
(currentScreening) =>
currentScreening.id !== screening.id &&
findMovie(movies, currentScreening).id ===
findMovie(movies, screening).id
);
};
const findFreeScreening = (
screenings: IScreening[],
screening: IScreening
): IScreening => {
return findNextScreenings(screenings, screening).find(
(nextScreening) =>
!findConflictingScreenings(screenings, nextScreening).length
);
};
const freeOtherScreening = findFreeScreening(
latestScreeningArray,
otherScreening
);
const freeScreening = findFreeScreening(
latestScreeningArray,
screening
);
if (freeOtherScreening || freeScreening) {
/* FREE SCREENING */
debugLog("free", {
screening: freeOtherScreening || freeScreening,
movies,
});
latestScreeningArray = deleteAllOtherScreenings(
latestScreeningArray,
freeOtherScreening || freeScreening,
movies
);
return true;
} else {
/* NO FREE SCREENINGS */
const decideAndMoveToNextStep = (
screenings: IScreening[],
screening1: IScreening,
screening2: IScreening
): boolean => {
latestScreeningArray = removeScreening(
deleteAllOtherScreenings(screenings, screening1, movies),
screening2
);
debugLog("recursion", {
recursionLevel,
array: latestScreeningArray,
});
recursionLevel++;
const nextStepOfBranchIsSolvable = processScreening(
latestScreeningArray,
findNextScreenings(screenings, screening2)[0],
`decideAndMoveToNextStep`
);
if (!nextStepOfBranchIsSolvable) {
debugLog("unsolvable", {
movies,
screening1,
screening2
});
latestScreeningArray = screenings;
}
return nextStepOfBranchIsSolvable;
};
const nextScreeningOfOther = findNextScreenings(
latestScreeningArray,
otherScreening
)[0];
if (nextScreeningOfOther) {
debugLog("decision", {
recursionLevel,
movies,
screening1: screening,
screening2: otherScreening,
});
return decideAndMoveToNextStep(
latestScreeningArray,
screening,
otherScreening
);
} else {
const nextScreening = findNextScreenings(
latestScreeningArray,
screening
)[0];
if (nextScreening) {
debugLog("decision", {
recursionLevel,
movies,
screening1: otherScreening,
screening2: screening,
});
return decideAndMoveToNextStep(
latestScreeningArray,
otherScreening,
screening
);
} else {
debugLog("unsolvable", {
movies,
screening1: screening,
screening2: otherScreening,
});
return false;
}
}
}
};
for (let i = conflictingScreenings.length - 1; i >= 0; i--) {
const branchResolved = resolveConflict(
screening,
[...conflictingScreenings].reverse()[i]
);
if (!branchResolved) {
latestScreeningArray = lastSafeArray;
break;
}
}
debugLog("noConflicts", {
movies,
screening
});
debugLog("recursion", {
recursionLevel,
array: latestScreeningArray
});
if (recursionLevel > 0) {
recursionLevel--;
}
return true;
} else {
const updatedScreenings = deleteAllOtherScreenings(
screenings,
screening,
movies
);
latestScreeningArray = updatedScreenings;
if (recursionLevel > 0) {
recursionLevel--;
}
return false;
}
};
for (let i = latestScreeningArray.length - 1; i >= 0; i--) {
if (!!latestScreeningArray[i]) {
lastSafeArray = latestScreeningArray;
lastSafeRecursionLevel = recursionLevel;
processScreening(
latestScreeningArray,
latestScreeningArray[i],
"overarching"
);
}
}
return latestScreeningArray;
};
我建议使用混合整数规划。 NPM 上有一个库 javascript-lp-solver，对于像这样的轻度使用来说可能没问题。
基本思想是为每部电影设置一个 0-1 变量，指示我们是否看过该电影的任何放映，并为每个放映设置一个 0-1 变量，指示我们是否看过该放映。我们想要最大化观看的电影数量（或者可能是一些更复杂的线性函数）。
约束有两种。对于每一次，我们不能在这段时间内参加超过一次的筛选（对于每一次，当时筛选变量的总和小于或等于 1）。这是在下面的代码中使用 sweep-line 算法处理的。对于每部电影，除非我们参加其中一场放映，否则我们看不到它（对于每部电影，该电影的放映变量之和减去大于或等于 0 的电影变量）。
我在下面的 JavaScript 中实现了这个（很差，因为我不流利，而且这个库上的 API 不是最好的）。
const movies = [
{
id: 1,
runtime: 121,
},
{
id: 2,
runtime: 116,
},
{
id: 3,
runtime: 144,
},
{
id: 4,
runtime: 96,
},
{
id: 5,
runtime: 108,
},
{
id: 6,
runtime: 117,
},
{
id: 7,
runtime: 92,
},
{
id: 8,
runtime: 110,
},
{
id: 9,
runtime: 90,
},
{
id: 10,
runtime: 99,
},
{
id: 11,
runtime: 62,
},
{
id: 12,
runtime: 116,
},
{
id: 13,
runtime: 85,
},
{
id: 14,
runtime: 92,
},
{
id: 15,
runtime: 85,
},
{
id: 16,
runtime: 90,
},
{
id: 17,
runtime: 103,
},
{
id: 18,
runtime: 113,
},
{
id: 19,
runtime: 72,
},
{
id: 20,
runtime: 109,
},
{
id: 21,
runtime: 109,
},
{
id: 22,
runtime: 142,
},
{
id: 23,
runtime: 96,
},
{
id: 24,
runtime: 73,
},
{
id: 25,
runtime: 86,
},
{
id: 26,
runtime: 106,
},
{
id: 27,
runtime: 97,
},
{
id: 28,
runtime: 100,
},
{
id: 29,
runtime: 146,
},
{
id: 30,
runtime: 146,
},
{
id: 31,
runtime: 146,
},
{
id: 32,
runtime: 108,
},
{
id: 33,
runtime: 89,
},
{
id: 34,
runtime: 126,
},
{
id: 35,
runtime: 121,
},
{
id: 36,
runtime: 150,
},
{
id: 37,
runtime: 108,
},
{
id: 38,
runtime: 103,
},
{
id: 39,
runtime: 130,
},
{
id: 40,
runtime: 83,
},
{
id: 41,
runtime: 136,
},
{
id: 42,
runtime: 85,
},
{
id: 43,
runtime: 179,
},
{
id: 44,
runtime: 106,
},
{
id: 45,
runtime: 107,
},
{
id: 46,
runtime: 93,
},
{
id: 47,
runtime: 75,
},
{
id: 48,
runtime: 86,
},
{
id: 49,
runtime: 80,
},
{
id: 50,
runtime: 80,
},
];
const screenings = [
{
id: 1,
date: "2021-11-18T23:15:00.000Z",
movieId: 18,
},
{
id: 2,
date: "2021-11-20T14:15:00.000Z",
movieId: 19,
},
{
id: 3,
date: "2021-11-19T21:00:00.000Z",
movieId: 19,
},
{
id: 4,
date: "2021-11-19T15:03:00.000Z",
movieId: 19,
},
{
id: 5,
date: "2021-11-19T23:04:00.000Z",
movieId: 20,
},
{
id: 6,
date: "2021-11-19T17:00:00.000Z",
movieId: 20,
},
{
id: 7,
date: "2021-11-25T20:00:00.000Z",
movieId: 20,
},
{
id: 8,
date: "2021-11-19T14:00:00.000Z",
movieId: 21,
},
{
id: 9,
date: "2021-11-19T20:00:00.000Z",
movieId: 21,
},
{
id: 10,
date: "2021-11-25T17:00:00.000Z",
movieId: 21,
},
{
id: 11,
date: "2021-11-19T21:00:00.000Z",
movieId: 22,
},
{
id: 12,
date: "2021-11-20T18:00:00.000Z",
movieId: 22,
},
{
id: 13,
date: "2021-11-19T16:00:00.000Z",
movieId: 23,
},
{
id: 14,
date: "2021-11-19T14:30:00.000Z",
movieId: 24,
},
{
id: 15,
date: "2021-11-19T23:30:00.000Z",
movieId: 24,
},
{
id: 16,
date: "2021-11-20T19:30:00.000Z",
movieId: 24,
},
{
id: 17,
date: "2021-11-20T14:30:00.000Z",
movieId: 25,
},
{
id: 18,
date: "2021-11-20T20:30:00.000Z",
movieId: 25,
},
{
id: 19,
date: "2021-11-21T22:30:00.000Z",
movieId: 25,
},
{
id: 20,
date: "2021-11-20T14:00:00.000Z",
movieId: 26,
},
{
id: 21,
date: "2021-11-20T20:00:00.000Z",
movieId: 26,
},
{
id: 22,
date: "2021-11-20T15:00:00.000Z",
movieId: 27,
},
{
id: 23,
date: "2021-11-20T21:00:00.000Z",
movieId: 27,
},
{
id: 24,
date: "2021-11-21T14:15:00.000Z",
movieId: 27,
},
{
id: 25,
date: "2021-11-20T18:00:00.000Z",
movieId: 28,
},
{
id: 26,
date: "2021-11-21T00:00:00.000Z",
movieId: 28,
},
{
id: 27,
date: "2021-11-21T17:15:00.000Z",
movieId: 28,
},
{
id: 28,
date: "2021-11-21T21:00:00.000Z",
movieId: 31,
},
{
id: 29,
date: "2021-11-20T21:00:00.000Z",
movieId: 31,
},
{
id: 30,
date: "2021-11-21T00:00:00.000Z",
movieId: 32,
},
{
id: 31,
date: "2021-11-29T00:00:00.000Z",
movieId: 32,
},
{
id: 32,
date: "2021-11-23T18:30:00.000Z",
movieId: 32,
},
{
id: 33,
date: "2021-11-21T14:00:00.000Z",
movieId: 33,
},
{
id: 34,
date: "2021-11-21T20:00:00.000Z",
movieId: 33,
},
{
id: 35,
date: "2021-11-22T22:30:00.000Z",
movieId: 33,
},
{
id: 36,
date: "2021-11-21T18:00:00.000Z",
movieId: 34,
},
{
id: 37,
date: "2021-11-22T23:15:00.000Z",
movieId: 34,
},
{
id: 38,
date: "2021-11-21T20:15:00.000Z",
movieId: 35,
},
{
id: 39,
date: "2021-11-27T21:00:00.000Z",
movieId: 35,
},
{
id: 40,
date: "2021-11-22T15:00:00.000Z",
movieId: 36,
},
{
id: 41,
date: "2021-11-23T00:00:00.000Z",
movieId: 36,
},
{
id: 42,
date: "2021-11-23T14:15:00.000Z",
movieId: 36,
},
{
id: 43,
date: "2021-11-22T13:45:00.000Z",
movieId: 37,
},
{
id: 44,
date: "2021-11-22T18:30:00.000Z",
movieId: 37,
},
{
id: 45,
date: "2021-11-22T21:30:00.000Z",
movieId: 37,
},
{
id: 46,
date: "2021-11-22T17:30:00.000Z",
movieId: 38,
},
{
id: 47,
date: "2021-11-22T23:30:00.000Z",
movieId: 38,
},
{
id: 48,
date: "2021-11-23T16:30:00.000Z",
movieId: 38,
},
{
id: 49,
date: "2021-11-22T21:00:00.000Z",
movieId: 39,
},
{
id: 50,
date: "2021-11-28T18:00:00.000Z",
movieId: 39,
},
{
id: 51,
date: "2021-11-23T18:00:00.000Z",
movieId: 40,
},
{
id: 52,
date: "2021-11-27T21:30:00.000Z",
movieId: 40,
},
{
id: 53,
date: "2021-11-24T18:00:00.000Z",
movieId: 41,
},
{
id: 54,
date: "2021-11-23T18:00:00.000Z",
movieId: 41,
},
{
id: 55,
date: "2021-11-25T18:00:00.000Z",
movieId: 41,
},
{
id: 58,
date: "2021-11-23T21:00:00.000Z",
movieId: 43,
},
{
id: 59,
date: "2021-11-24T21:00:00.000Z",
movieId: 43,
},
{
id: 60,
date: "2021-11-24T14:30:00.000Z",
movieId: 44,
},
{
id: 61,
date: "2021-11-24T20:30:00.000Z",
movieId: 44,
},
{
id: 62,
date: "2021-11-25T16:30:00.000Z",
movieId: 44,
},
{
id: 63,
date: "2021-11-25T21:00:00.000Z",
movieId: 45,
},
{
id: 64,
date: "2021-11-26T15:00:00.000Z",
movieId: 45,
},
{
id: 70,
date: "2021-11-24T15:00:00.000Z",
movieId: 48,
},
{
id: 71,
date: "2021-11-24T21:00:00.000Z",
movieId: 48,
},
{
id: 72,
date: "2021-11-26T00:00:00.000Z",
movieId: 48,
},
{
id: 76,
date: "2021-11-24T14:00:00.000Z",
movieId: 50,
},
{
id: 77,
date: "2021-11-24T20:00:00.000Z",
movieId: 50,
},
{
id: 78,
date: "2021-11-27T17:00:00.000Z",
movieId: 50,
},
];
let model = {
optimize: "movieSeen",
opType: "max",
constraints: {},
variables: {},
ints: {},
};
let constraintId = 1000;
for (const movie of movies) {
++constraintId;
model.constraints[constraintId] = { max: 1 };
model.variables["m" + movie.id] = { movieSeen: 1 };
model.variables["m" + movie.id][constraintId] = 1;
++constraintId;
model.constraints["sm" + movie.id] = { min: 0 };
model.variables["m" + movie.id]["sm" + movie.id] = -1;
}
for (const screening of screenings) {
++constraintId;
model.constraints[constraintId] = { min: 0 };
model.variables["s" + screening.id] = { constraintId: 1 };
model.variables["s" + screening.id]["sm" + screening.movieId] = 1;
model.ints["s" + screening.id] = 1;
}
let runtimes = {};
for (const movie of movies) {
runtimes[movie.id] = movie.runtime;
}
let events = [];
for (const screening of screenings) {
const start = Date.parse(screening.date);
events.push({ date: start, isStart: true, id: screening.id });
const finish = start + runtimes[screening.movieId] * 60 * 1000;
events.push({ date: finish, isStart: false, id: screening.id });
}
events.sort(function (a, b) {
return a.date - b.date;
});
let previousIsStart = false;
let nowPlaying = {};
for (const event of events) {
if (event.isStart) {
nowPlaying[event.id] = true;
previousIsStart = true;
} else {
if (previousIsStart) {
++constraintId;
model.constraints[constraintId] = { max: 1 };
for (const id of Object.keys(nowPlaying)) {
model.variables["s" + id][constraintId] = 1;
}
}
delete nowPlaying[event.id];
previousIsStart = false;
}
}
let solver = require("javascript-lp-solver");
let results = solver.Solve(model);
console.log(results);
输出：
{
feasible: true,
result: 27,
bounded: true,
isIntegral: true,
s1: 1,
s64: 1,
s12: 1,
s15: 1,
s42: 1,
s20: 1,
s24: 1,
s29: 1,
s31: 1,
s37: 1,
s19: 1,
s46: 1,
s51: 1,
s53: 1,
s58: 1,
s71: 1,
s13: 1,
s3: 1,
s8: 1,
s34: 1,
s7: 1,
s26: 1,
s39: 1,
s43: 1,
s49: 1,
s76: 1,
s62: 1,
m18: 1,
m19: 1,
m20: 1,
m21: 1,
m22: 1,
m23: 1,
m24: 1,
m25: 1,
m26: 1,
m27: 1,
m28: 1,
m31: 1,
m32: 1,
m33: 1,
m34: 1,
m35: 1,
m36: 1,
m37: 1,
m38: 1,
m39: 1,
m40: 1,
m41: 1,
m43: 1,
m44: 1,
m45: 1,
m48: 1,
m50: 1
}
我正在尝试编写一种算法，该算法采用一系列事件（在本例中为电影放映 - 每部电影通常有不止一次放映，尽管情况并非总是如此）和 returns事件的最佳可能组合，即牺牲最少电影数量的事件。
我想出了这个我手动应用的算法，但我试图将其转换为代码并遇到了一些麻烦。我所做的（手动）是逐个筛选，检查它是否与任何其他筛选有冲突。如果是这样，它将通过选择两部冲突电影中的一部*（电影 A），删除电影 A 的所有其他放映，并删除电影B的那个放映。之后，它会寻找另一个电影B的放映，检查是否有冲突，然后重复这个过程。
* 通常是我当前正在检查的那个，但某些标准可能会影响决定，例如如果两部相互冲突的电影中有一部在其他地方免费（无冲突）放映，我只会选择那部并以这种方式解决冲突。反之，如果两部电影中有一部没有其他放映，我会选择那部。
最终这个“分支”最终会进行免费（无冲突）放映，这意味着整个分支都已解决（即可以在不牺牲任何其他电影的情况下观看所有涉及的电影），或者它会陷入僵局，这意味着这些决定的组合并没有带来完美的解决方案。在这种情况下，人们会回到递归的一个层次（即回到一个决定）并尝试选择另一个筛选。如果这不起作用，请返回另一个级别并重试。如果该分支中没有导致解决分支的决定组合，则必须由人类做出决定以牺牲导致问题的电影之一。
这几乎就是我要编写的代码，我以一种非常意识流的方式写了一个尝试，只是想尽快把它弄出来，因为我很兴奋，没有想得太远，只是解决问题。它适用于我正在尝试的电影节，它有点小（同时不超过 4 次放映），但是当我在更大的电影节上尝试它时崩溃（有时同时放映 6 次以上）。它超过了最大堆栈大小，可能是因为代码中的问题，尽管我不确定它是否只是 运行 正确并且只是进入那些递归级别。关于这一点，不确定使用 while 循环而不是递归是否可以更好地解决这个问题。
昨天我决定放弃我写的算法并以更好的计划方式从头开始，发现我认为展望未来的主要 2 个问题是：
- 当分支失败时算法“返回”并切换其先前决策的能力。这是该算法的核心机制，但我正在努力想出一种对其进行编码的好方法。在我之前的一个中，我实现了一个“检查点”系统，如果一个分支失败，它会恢复到最后一个检查点并从那里继续，如果它成功，它会把那个标记为新的检查点。但这只适用于顶层，不适用于“内部”决策。
- 事实上，大多数日程表都有不止一种解决方案。如果解决方案是完美的（即没有牺牲任何电影），那么问题就很小，无论哪种方式你都不会错过任何电影，最多你将被剥夺在同一部电影的几场放映之间进行选择的权利。但如果没有完美的解决方案，现在的选择可能是在你真正想看的 2 部电影和你不太关心的 2 部电影之间做出选择。这意味着该算法需要遍历每个可能的筛选组合以找到最佳组合，如果没有完美的解决方案，它会向您展示不同的可能性。但这将是暴力强制问题（除非绝对必要）并不是我正在寻找的问题。
对于此事的任何帮助或指导，我将不胜感激。作为参考，我正在用 Typescript + React + Next.js 写这篇文章，但我认为这是一个更一般的 CS 问题，所以再次感谢任何帮助。
当前的算法和模拟数据可以在这里找到：https://jsfiddle.net/procz/82n3jxLb/
const findBestSchedule = (
screeningData: IScreening[],
movies: IMovie[]
): IScreening[] => {
const debugLog = (type: string, args) => {
if (!DEBUG_LOG) return;
if (type === "process") {
return console.log(
`processing ${findMovie(
movies,
args.screening
).name.toUpperCase()} ${args.screening.date.getDate()} ${args.screening.date.getHours()}hs - called from ${
args.calledFrom
}, currentArray:`,
args.screenings
);
}
if (type === "conflict") {
return console.log(
`conflict between ${findMovie(
args.movies,
args.screening1
).name.toUpperCase()} ${args.screening1.date.getDate()} ${args.screening1.date.getHours()}hs and ${findMovie(
movies,
args.screening2
).name.toUpperCase()} ${args.screening2.date.getDate()} ${args.screening2.date.getHours()}hs`
);
}
if (type === "free") {
return console.log(
`${findMovie(
args.movies,
args.screening
).name.toUpperCase()} ${args.screening.date.getDate()} ${args.screening.date.getHours()}hs is free, deleting all other ${findMovie(
args.movies,
args.screening
).name.toUpperCase()}`
);
}
if (type === "recursion") {
return console.log(args.recursionLevel, args.array);
}
if (type === "unsolvable") {
return console.log(
`unsolvable conflict between ${findMovie(
args.movies,
args.screening1
).name.toUpperCase()} and ${findMovie(
args.movies,
args.screening2
).name.toUpperCase()}, backtracking`
);
}
if (type === "decision") {
return console.log(
`recursion level: ${args.recursionLevel} - choosing ${findMovie(
args.movies,
args.screening1
).name.toUpperCase()} ${args.screening1.date.getDate()} ${args.screening1.date.getHours()}hs, deleting ${findMovie(
args.movies,
args.screening2
).name.toUpperCase()} ${args.screening2.date.getDate()} ${args.screening2.date.getHours()}hs, deleting all other ${findMovie(
args.movies,
args.screening1
).name.toUpperCase()}`
);
}
if (type === "noConflict") {
return console.log(
`no conflicts found for ${findMovie(
args.movies,
args.screening
).name.toUpperCase()} ${args.screening.date.getDate()} ${args.screening.date.getHours()}hs, deleting all other ${findMovie(
args.movies,
args.screening
).name.toUpperCase()}`
);
}
};
const sortedScreenings = [...screeningData].sort(
(a, b) => b.date.getTime() - a.date.getTime()
);
let latestScreeningArray = sortedScreenings;
let recursionLevel = 0;
let lastSafeArray = latestScreeningArray;
let lastSafeRecursionLevel = recursionLevel;
const processScreening = (
screenings: IScreening[],
screening: IScreening,
calledFrom ? : string
): boolean => {
debugLog("process", {
screening,
calledFrom,
screenings
});
const findConflictingScreenings = (
screenings: IScreening[],
screening: IScreening
): IScreening[] => {
if (!screenings) return [];
return [...screenings].filter(
(otherScreening) =>
screening.id !== otherScreening ? .id &&
screeningsOverlap(screening, otherScreening, movies)
);
};
const conflictingScreenings = findConflictingScreenings(
screenings,
screening
);
if (conflictingScreenings.length) {
const resolveConflict = (
screening: IScreening,
otherScreening: IScreening
): boolean => {
debugLog("conflict", {
screening1: screening,
screening2: otherScreening,
movies,
});
const findNextScreenings = (
screenings: IScreening[],
screening: IScreening
): IScreening[] => {
return [...screenings]
.reverse()
.filter(
(currentScreening) =>
currentScreening.id !== screening.id &&
findMovie(movies, currentScreening).id ===
findMovie(movies, screening).id
);
};
const findFreeScreening = (
screenings: IScreening[],
screening: IScreening
): IScreening => {
return findNextScreenings(screenings, screening).find(
(nextScreening) =>
!findConflictingScreenings(screenings, nextScreening).length
);
};
const freeOtherScreening = findFreeScreening(
latestScreeningArray,
otherScreening
);
const freeScreening = findFreeScreening(
latestScreeningArray,
screening
);
if (freeOtherScreening || freeScreening) {
/* FREE SCREENING */
debugLog("free", {
screening: freeOtherScreening || freeScreening,
movies,
});
latestScreeningArray = deleteAllOtherScreenings(
latestScreeningArray,
freeOtherScreening || freeScreening,
movies
);
return true;
} else {
/* NO FREE SCREENINGS */
const decideAndMoveToNextStep = (
screenings: IScreening[],
screening1: IScreening,
screening2: IScreening
): boolean => {
latestScreeningArray = removeScreening(
deleteAllOtherScreenings(screenings, screening1, movies),
screening2
);
debugLog("recursion", {
recursionLevel,
array: latestScreeningArray,
});
recursionLevel++;
const nextStepOfBranchIsSolvable = processScreening(
latestScreeningArray,
findNextScreenings(screenings, screening2)[0],
`decideAndMoveToNextStep`
);
if (!nextStepOfBranchIsSolvable) {
debugLog("unsolvable", {
movies,
screening1,
screening2
});
latestScreeningArray = screenings;
}
return nextStepOfBranchIsSolvable;
};
const nextScreeningOfOther = findNextScreenings(
latestScreeningArray,
otherScreening
)[0];
if (nextScreeningOfOther) {
debugLog("decision", {
recursionLevel,
movies,
screening1: screening,
screening2: otherScreening,
});
return decideAndMoveToNextStep(
latestScreeningArray,
screening,
otherScreening
);
} else {
const nextScreening = findNextScreenings(
latestScreeningArray,
screening
)[0];
if (nextScreening) {
debugLog("decision", {
recursionLevel,
movies,
screening1: otherScreening,
screening2: screening,
});
return decideAndMoveToNextStep(
latestScreeningArray,
otherScreening,
screening
);
} else {
debugLog("unsolvable", {
movies,
screening1: screening,
screening2: otherScreening,
});
return false;
}
}
}
};
for (let i = conflictingScreenings.length - 1; i >= 0; i--) {
const branchResolved = resolveConflict(
screening,
[...conflictingScreenings].reverse()[i]
);
if (!branchResolved) {
latestScreeningArray = lastSafeArray;
break;
}
}
debugLog("noConflicts", {
movies,
screening
});
debugLog("recursion", {
recursionLevel,
array: latestScreeningArray
});
if (recursionLevel > 0) {
recursionLevel--;
}
return true;
} else {
const updatedScreenings = deleteAllOtherScreenings(
screenings,
screening,
movies
);
latestScreeningArray = updatedScreenings;
if (recursionLevel > 0) {
recursionLevel--;
}
return false;
}
};
for (let i = latestScreeningArray.length - 1; i >= 0; i--) {
if (!!latestScreeningArray[i]) {
lastSafeArray = latestScreeningArray;
lastSafeRecursionLevel = recursionLevel;
processScreening(
latestScreeningArray,
latestScreeningArray[i],
"overarching"
);
}
}
return latestScreeningArray;
};
我建议使用混合整数规划。 NPM 上有一个库 javascript-lp-solver，对于像这样的轻度使用来说可能没问题。
基本思想是为每部电影设置一个 0-1 变量，指示我们是否看过该电影的任何放映，并为每个放映设置一个 0-1 变量，指示我们是否看过该放映。我们想要最大化观看的电影数量（或者可能是一些更复杂的线性函数）。
约束有两种。对于每一次，我们不能在这段时间内参加超过一次的筛选（对于每一次，当时筛选变量的总和小于或等于 1）。这是在下面的代码中使用 sweep-line 算法处理的。对于每部电影，除非我们参加其中一场放映，否则我们看不到它（对于每部电影，该电影的放映变量之和减去大于或等于 0 的电影变量）。
我在下面的 JavaScript 中实现了这个（很差，因为我不流利，而且这个库上的 API 不是最好的）。
const movies = [
{
id: 1,
runtime: 121,
},
{
id: 2,
runtime: 116,
},
{
id: 3,
runtime: 144,
},
{
id: 4,
runtime: 96,
},
{
id: 5,
runtime: 108,
},
{
id: 6,
runtime: 117,
},
{
id: 7,
runtime: 92,
},
{
id: 8,
runtime: 110,
},
{
id: 9,
runtime: 90,
},
{
id: 10,
runtime: 99,
},
{
id: 11,
runtime: 62,
},
{
id: 12,
runtime: 116,
},
{
id: 13,
runtime: 85,
},
{
id: 14,
runtime: 92,
},
{
id: 15,
runtime: 85,
},
{
id: 16,
runtime: 90,
},
{
id: 17,
runtime: 103,
},
{
id: 18,
runtime: 113,
},
{
id: 19,
runtime: 72,
},
{
id: 20,
runtime: 109,
},
{
id: 21,
runtime: 109,
},
{
id: 22,
runtime: 142,
},
{
id: 23,
runtime: 96,
},
{
id: 24,
runtime: 73,
},
{
id: 25,
runtime: 86,
},
{
id: 26,
runtime: 106,
},
{
id: 27,
runtime: 97,
},
{
id: 28,
runtime: 100,
},
{
id: 29,
runtime: 146,
},
{
id: 30,
runtime: 146,
},
{
id: 31,
runtime: 146,
},
{
id: 32,
runtime: 108,
},
{
id: 33,
runtime: 89,
},
{
id: 34,
runtime: 126,
},
{
id: 35,
runtime: 121,
},
{
id: 36,
runtime: 150,
},
{
id: 37,
runtime: 108,
},
{
id: 38,
runtime: 103,
},
{
id: 39,
runtime: 130,
},
{
id: 40,
runtime: 83,
},
{
id: 41,
runtime: 136,
},
{
id: 42,
runtime: 85,
},
{
id: 43,
runtime: 179,
},
{
id: 44,
runtime: 106,
},
{
id: 45,
runtime: 107,
},
{
id: 46,
runtime: 93,
},
{
id: 47,
runtime: 75,
},
{
id: 48,
runtime: 86,
},
{
id: 49,
runtime: 80,
},
{
id: 50,
runtime: 80,
},
];
const screenings = [
{
id: 1,
date: "2021-11-18T23:15:00.000Z",
movieId: 18,
},
{
id: 2,
date: "2021-11-20T14:15:00.000Z",
movieId: 19,
},
{
id: 3,
date: "2021-11-19T21:00:00.000Z",
movieId: 19,
},
{
id: 4,
date: "2021-11-19T15:03:00.000Z",
movieId: 19,
},
{
id: 5,
date: "2021-11-19T23:04:00.000Z",
movieId: 20,
},
{
id: 6,
date: "2021-11-19T17:00:00.000Z",
movieId: 20,
},
{
id: 7,
date: "2021-11-25T20:00:00.000Z",
movieId: 20,
},
{
id: 8,
date: "2021-11-19T14:00:00.000Z",
movieId: 21,
},
{
id: 9,
date: "2021-11-19T20:00:00.000Z",
movieId: 21,
},
{
id: 10,
date: "2021-11-25T17:00:00.000Z",
movieId: 21,
},
{
id: 11,
date: "2021-11-19T21:00:00.000Z",
movieId: 22,
},
{
id: 12,
date: "2021-11-20T18:00:00.000Z",
movieId: 22,
},
{
id: 13,
date: "2021-11-19T16:00:00.000Z",
movieId: 23,
},
{
id: 14,
date: "2021-11-19T14:30:00.000Z",
movieId: 24,
},
{
id: 15,
date: "2021-11-19T23:30:00.000Z",
movieId: 24,
},
{
id: 16,
date: "2021-11-20T19:30:00.000Z",
movieId: 24,
},
{
id: 17,
date: "2021-11-20T14:30:00.000Z",
movieId: 25,
},
{
id: 18,
date: "2021-11-20T20:30:00.000Z",
movieId: 25,
},
{
id: 19,
date: "2021-11-21T22:30:00.000Z",
movieId: 25,
},
{
id: 20,
date: "2021-11-20T14:00:00.000Z",
movieId: 26,
},
{
id: 21,
date: "2021-11-20T20:00:00.000Z",
movieId: 26,
},
{
id: 22,
date: "2021-11-20T15:00:00.000Z",
movieId: 27,
},
{
id: 23,
date: "2021-11-20T21:00:00.000Z",
movieId: 27,
},
{
id: 24,
date: "2021-11-21T14:15:00.000Z",
movieId: 27,
},
{
id: 25,
date: "2021-11-20T18:00:00.000Z",
movieId: 28,
},
{
id: 26,
date: "2021-11-21T00:00:00.000Z",
movieId: 28,
},
{
id: 27,
date: "2021-11-21T17:15:00.000Z",
movieId: 28,
},
{
id: 28,
date: "2021-11-21T21:00:00.000Z",
movieId: 31,
},
{
id: 29,
date: "2021-11-20T21:00:00.000Z",
movieId: 31,
},
{
id: 30,
date: "2021-11-21T00:00:00.000Z",
movieId: 32,
},
{
id: 31,
date: "2021-11-29T00:00:00.000Z",
movieId: 32,
},
{
id: 32,
date: "2021-11-23T18:30:00.000Z",
movieId: 32,
},
{
id: 33,
date: "2021-11-21T14:00:00.000Z",
movieId: 33,
},
{
id: 34,
date: "2021-11-21T20:00:00.000Z",
movieId: 33,
},
{
id: 35,
date: "2021-11-22T22:30:00.000Z",
movieId: 33,
},
{
id: 36,
date: "2021-11-21T18:00:00.000Z",
movieId: 34,
},
{
id: 37,
date: "2021-11-22T23:15:00.000Z",
movieId: 34,
},
{
id: 38,
date: "2021-11-21T20:15:00.000Z",
movieId: 35,
},
{
id: 39,
date: "2021-11-27T21:00:00.000Z",
movieId: 35,
},
{
id: 40,
date: "2021-11-22T15:00:00.000Z",
movieId: 36,
},
{
id: 41,
date: "2021-11-23T00:00:00.000Z",
movieId: 36,
},
{
id: 42,
date: "2021-11-23T14:15:00.000Z",
movieId: 36,
},
{
id: 43,
date: "2021-11-22T13:45:00.000Z",
movieId: 37,
},
{
id: 44,
date: "2021-11-22T18:30:00.000Z",
movieId: 37,
},
{
id: 45,
date: "2021-11-22T21:30:00.000Z",
movieId: 37,
},
{
id: 46,
date: "2021-11-22T17:30:00.000Z",
movieId: 38,
},
{
id: 47,
date: "2021-11-22T23:30:00.000Z",
movieId: 38,
},
{
id: 48,
date: "2021-11-23T16:30:00.000Z",
movieId: 38,
},
{
id: 49,
date: "2021-11-22T21:00:00.000Z",
movieId: 39,
},
{
id: 50,
date: "2021-11-28T18:00:00.000Z",
movieId: 39,
},
{
id: 51,
date: "2021-11-23T18:00:00.000Z",
movieId: 40,
},
{
id: 52,
date: "2021-11-27T21:30:00.000Z",
movieId: 40,
},
{
id: 53,
date: "2021-11-24T18:00:00.000Z",
movieId: 41,
},
{
id: 54,
date: "2021-11-23T18:00:00.000Z",
movieId: 41,
},
{
id: 55,
date: "2021-11-25T18:00:00.000Z",
movieId: 41,
},
{
id: 58,
date: "2021-11-23T21:00:00.000Z",
movieId: 43,
},
{
id: 59,
date: "2021-11-24T21:00:00.000Z",
movieId: 43,
},
{
id: 60,
date: "2021-11-24T14:30:00.000Z",
movieId: 44,
},
{
id: 61,
date: "2021-11-24T20:30:00.000Z",
movieId: 44,
},
{
id: 62,
date: "2021-11-25T16:30:00.000Z",
movieId: 44,
},
{
id: 63,
date: "2021-11-25T21:00:00.000Z",
movieId: 45,
},
{
id: 64,
date: "2021-11-26T15:00:00.000Z",
movieId: 45,
},
{
id: 70,
date: "2021-11-24T15:00:00.000Z",
movieId: 48,
},
{
id: 71,
date: "2021-11-24T21:00:00.000Z",
movieId: 48,
},
{
id: 72,
date: "2021-11-26T00:00:00.000Z",
movieId: 48,
},
{
id: 76,
date: "2021-11-24T14:00:00.000Z",
movieId: 50,
},
{
id: 77,
date: "2021-11-24T20:00:00.000Z",
movieId: 50,
},
{
id: 78,
date: "2021-11-27T17:00:00.000Z",
movieId: 50,
},
];
let model = {
optimize: "movieSeen",
opType: "max",
constraints: {},
variables: {},
ints: {},
};
let constraintId = 1000;
for (const movie of movies) {
++constraintId;
model.constraints[constraintId] = { max: 1 };
model.variables["m" + movie.id] = { movieSeen: 1 };
model.variables["m" + movie.id][constraintId] = 1;
++constraintId;
model.constraints["sm" + movie.id] = { min: 0 };
model.variables["m" + movie.id]["sm" + movie.id] = -1;
}
for (const screening of screenings) {
++constraintId;
model.constraints[constraintId] = { min: 0 };
model.variables["s" + screening.id] = { constraintId: 1 };
model.variables["s" + screening.id]["sm" + screening.movieId] = 1;
model.ints["s" + screening.id] = 1;
}
let runtimes = {};
for (const movie of movies) {
runtimes[movie.id] = movie.runtime;
}
let events = [];
for (const screening of screenings) {
const start = Date.parse(screening.date);
events.push({ date: start, isStart: true, id: screening.id });
const finish = start + runtimes[screening.movieId] * 60 * 1000;
events.push({ date: finish, isStart: false, id: screening.id });
}
events.sort(function (a, b) {
return a.date - b.date;
});
let previousIsStart = false;
let nowPlaying = {};
for (const event of events) {
if (event.isStart) {
nowPlaying[event.id] = true;
previousIsStart = true;
} else {
if (previousIsStart) {
++constraintId;
model.constraints[constraintId] = { max: 1 };
for (const id of Object.keys(nowPlaying)) {
model.variables["s" + id][constraintId] = 1;
}
}
delete nowPlaying[event.id];
previousIsStart = false;
}
}
let solver = require("javascript-lp-solver");
let results = solver.Solve(model);
console.log(results);
输出：
{
feasible: true,
result: 27,
bounded: true,
isIntegral: true,
s1: 1,
s64: 1,
s12: 1,
s15: 1,
s42: 1,
s20: 1,
s24: 1,
s29: 1,
s31: 1,
s37: 1,
s19: 1,
s46: 1,
s51: 1,
s53: 1,
s58: 1,
s71: 1,
s13: 1,
s3: 1,
s8: 1,
s34: 1,
s7: 1,
s26: 1,
s39: 1,
s43: 1,
s49: 1,
s76: 1,
s62: 1,
m18: 1,
m19: 1,
m20: 1,
m21: 1,
m22: 1,
m23: 1,
m24: 1,
m25: 1,
m26: 1,
m27: 1,
m28: 1,
m31: 1,
m32: 1,
m33: 1,
m34: 1,
m35: 1,
m36: 1,
m37: 1,
m38: 1,
m39: 1,
m40: 1,
m41: 1,
m43: 1,
m44: 1,
m45: 1,
m48: 1,
m50: 1
}