Opened by renee at 2005-02-23 01:50
User since
2003-08-04
5873 Artikel
ModeratorIn
![[Homepage]](/battie/theme/default/homepage.gif)
2003-08-04
5873 Artikel
ModeratorIn
Dein Problem könnte man graphentheoretisch angehen. Jeder Termin ist eine Ecke, zwei Ecken sind benachbart, wenn die Termine sich überlappen (dazu wäre zu klären, ob sich 8-10 mit 10-11:30 überlappt oder nicht, aber das nur am Rande).
Dann musst Du den Graphen nur noch so einfärben, dass benachbarte Ecken verschiedene Farben bekommen. (Die Farben entsprechen dann den Spalten Deines Kalenders.)
Dieses Problem ist bekannter Weise NP-hart, allerdings wirst Du ja wahrscheinlich keine riesigen Terminmengen pro Tag haben, so dass Du Dir eventuell die exakte Backtracking-Lösung (laufzeittechnisch) leisten kannst.
Falls nicht, kann ich Dir einen ganzen Haufen an schnelleren (aber nicht optimalen) Algorithmen nennen, denn über Färbungsalgorithmen von Graphen habe ich meine Diplomarbeit geschrieben. Ich schreib zunächst mal den Backtracking-Algorithmus ab, wahrscheinlich reicht der:
(Ist allerdings C++)
Ich hoffe, das ist zumindestens ein Einstiegspunkt :-)
Ich kann aber gern auch bei einer Perl-Umsetzung helfen.
Dann musst Du den Graphen nur noch so einfärben, dass benachbarte Ecken verschiedene Farben bekommen. (Die Farben entsprechen dann den Spalten Deines Kalenders.)
Dieses Problem ist bekannter Weise NP-hart, allerdings wirst Du ja wahrscheinlich keine riesigen Terminmengen pro Tag haben, so dass Du Dir eventuell die exakte Backtracking-Lösung (laufzeittechnisch) leisten kannst.
Falls nicht, kann ich Dir einen ganzen Haufen an schnelleren (aber nicht optimalen) Algorithmen nennen, denn über Färbungsalgorithmen von Graphen habe ich meine Diplomarbeit geschrieben. Ich schreib zunächst mal den Backtracking-Algorithmus ab, wahrscheinlich reicht der:
(Ist allerdings C++)
Code: (dl
)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
Vertex backtrackingColoring(const Graph &g, CSet &c)
{
Vertex k = 0;
bool success = false;
while (!success) {
++k;
success = kBacktracking(g, k, c);
}
return k;
} /* backtrackingColoring */
bool kBacktracking(const Graph &g, const Color k, CSet &c)
{
if (k < 1)
error("kBacktracking", "Farbe %d zu klein.", k);
/**************************************************************************
* Initialisierungen: *
**************************************************************************/
const Vertex n = g.getn();
c.resize(n);
for (Vertex i=0; i<n; ++i)
c[i] = 0;
/**************************************************************************
* Aufruf der rekursiven Untersuchung: *
**************************************************************************/
return btcTry(g, 0, k, c);
} /* kBacktracking */
bool btcTry(const Graph &g, const Vertex i, const Color k, CSet &c)
{
/**************************************************************************
* Initialisierungen: *
**************************************************************************/
const Vertex n = g.getn();
Color color = 0;
bool q = false;
/**************************************************************************
* Fehler abfangen: *
**************************************************************************/
if (i >= n)
error("btcTry", "Ecke i = %d ist außerhalb des zulässigen Bereiches "
"[0, %d]", i, n-1);
if (k < 1 || k > static_cast<Color>(n))
error("btcTry", "Farbe k = %d ist außerhalb des zulässigen Bereiches "
"[1, %d]", k, n);
/**************************************************************************
* Schleife: *
**************************************************************************/
while (q == false && color != k) {
++color;
/*** Abbruch, falls i==0 und color>1: ***/
if (i == 0 && color > 1)
break;
if (btcPossible(g, i, color, c)) {
c[i] = color;
if (i < n-1) {
q = btcTry(g, i+1, k, c);
if (!q)
c[i] = 0;
}
else
q = true;
}
}
return q;
} /* btcTry */
bool btcPossible(const Graph &g, const Vertex i, const Color color,
const CSet &c)
{
VSet N;
g.getNeighbours(i, N);
for (Vertex j=0; j<N.size(); ++j)
if (c[N[j]] == color)
return false;
return true;
} /* btcPossible */
Ich hoffe, das ist zumindestens ein Einstiegspunkt :-)
Ich kann aber gern auch bei einer Perl-Umsetzung helfen.
s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;
use strict; use warnings; Link zu meiner Perlseite
use strict; use warnings; Link zu meiner Perlseite