Intervall Partitioning in java

[joker123]

Hallo,

wir haben als Aufgabe bekommen, ein "intervall partitioning" zu programmieren...
mein Problem ist, ich hab keinen Plan wie ich überhaupt anfangen soll, ich hab zwar Überlegungen schon ein wenig im Kopf, aber halt noch nicht in java...

ich denken, so müsste es irgendwie lösbar sein

Teile die Menge aller Intervalle in disjunkte Teilmengen auf, deren Vereinigung wieder die Gesamtmenge ergibt. Lösungsraum ist damit die Menge aller Partitionierungen der eingegebenen Intervalle.

Eine Partitionierung ist Lösung, falls in jeder Partition gilt, dass alle Intervalle kompatibel sind

wobei unter kompatibel verstanden wird:

s(i) >= f(j) oder s(j) >= f(i)

wobei s = start und f = finish bedeudet...also startzeit und endzeit eines Intervalls...
somit wären Überschneidungen von 2 Intervallen ausgeschlossen

wäre froh, wenn mir vielleicht jemand weiterhelfen könnte

danke
mfG

 

[SlaterB]

> ich hab zwar Überlegungen schon ein wenig im Kopf, aber halt noch nicht in java...

kannst du was zu den Überlegungen erzählen? alles nach diesem Satz klingt ja allein nach Aufgabenstellung, nix von Lösung

 

[joker123]

nee, also die Aufgabenstellung ist eigentlich nur "implementieren sie einen Algorithmus Intervall Partitioning"

aber zu meiner Vorgehensweise...
ich hab eine Anzahl von Intervallen, x. (x >= 1, sonst macht es keinen Sinn)
so, nun würde ich jeweils für Startzeiten und Endzeiten einen Array anlegen ( int[] s, int[] f)

anschließend würd ich dann mal die Anzahl an Intervallen durchlaufen

public static int intervallPartitioning(int m, int[] s, int[] f)
{
   int [] start = s;
   int [] finish = f;

   for (int i=0; i<=m; i++)
   {
       // vergleichen ob startzeit(i) >= endzeit(j) ODER startzeit(j) >= endzeit(i) ist
       if (s(i) >= f(j) || (s(j) >= f(i))

ich weiß, dass es noch nicht viel ist, aber ich bin neu was java angeht...
ich komm nicht drauf, wie ich das mit dieser if-Bedingung hinkriegen soll, also mit den Indizes, da "j" in meinem Code noch gar nicht benutzt wird...
deshalb hoffe ich, dass mir vielleicht jemand weiterhelfen könnte

danke
mfG

 

[tfa]

Sieht aus, als ob der Algorithmus noch gefunden werden muss. Das geht auch ohne Java.
Formulier ihn doch erstmal in Pseudocode, bei der Umsetzung wird dir hier sicherlich geholfen.

 

[SlaterB]

wie gesagt: erst in Worten erzählen, Java überhaupt nicht,

dein Code und deine Zeilen enthalten eigentlich gar keine Lösung, Startzeiten und Endzeiten aufzutrennen ist schonmal schlecht,
ansonsten kümmerst du dich vielleicht um den Test, nicht aber um das Finden von Lösungen an sich
-----

alles fängt mit einem Beispiel an, vier Intervalle:
A = 2-5
B = 6-7
C = 4-5
D = 5-7

(1)
eine denkbare Partitionierung ist alle 4 Intervalle in einer Partition,
wenn man die prüft (Java-Untermethode, nicht weiter spannend) wird man feststellen, dass sich die Intervalle überschneiden
-> keine Lösung

(2)
noch eine Variante ist, für jedes Intervall eine separate Partition anzulegen, dies ist eine triviale Variante, die immer eine Lösung ist

(3)
interessanter wirds, wenn A+B in einer Partition stehen und C+D in einer anderen,

usw.

(1), (2), (3) sind drei mögliche Partitionierungen, alle Möglichkeiten muss man finden

ein Ansatz:
man kann sich eine Notation ausdenken, jedem der vier Intervalle eine Zahl x zuordnen, die die Einordnung in die Partition x bedeutet

Partitionierung (1) ist dann 1111, alle 4 Intervalle kommen in Partition 1
Partitionierung (2) ist dann 1234, alle 4 Intervalle kommen in eigene 4 unterschiedliche Partitionen
Partitionierung (3) ist dann 1122,

die Menge aller möglichen Partitionierungen kann man dann mehr oder weniger leicht sehen:
1111
1112
(1113 macht keinen Sinn)
1121
1122
1123
usw.
das in Java umzusetzen ist schon nicht ganz trivial, Rekursion hilft,
oder komplexe Schleife mit Array, Zählvariablen usw.

----

zweiter Ansatz:
man kann sich die Rekursion (jetzt wirklich halb in Java gedacht) auch etwas plastischer vorstellen:
das erste Intervall kommt eh immer in die erste Partition,

das zweite Intervall kommt entweder mit in die erste Partition oder in eine zweite neue,
beide Varianten ausprobieren, mit Backtracking zwischendurch den Rest positionieren

fürs x-te Intervall gilt: schauen wie viele Partitionen da sind,
nacheinander in alle vorhandenen einfügen (dazwischen immer per Rekursion weitersuchen)
sowie eine neue Partition aufmachen (+ weitersuchen)

diese Verarbeitung hat den Vorteil, dass man beim Einfügen in eine Partition gleich prüfen kann, ob die Zeit-Bedingung verletzt ist,
dann kann man den aktuellen Versuch abbrechen, egal wie die restlichen Intervalle zu platzieren sind

-----

so, das waren jetzt mehr Tipps als ich geben wollte, aber alle noch allgemein, hast noch genug zu programmieren
wenn dir Rekursion + Backtracking nix sagen, dann das vorher nachschlagen

 

[joker123]

ok, also ich bin mir dabei nicht sicher
aber ich versuchs mal hiermit

a = {1};   // startmenge
letztes_element = 1;   // zuletzt hinzugefügtes element
for i=1 to m do            
    if (((s(i) >= f(letztes_element)) OR (s(letztes_element) >= f(i)) then  // keine Überschneidung
        a = a U {i}   // i wird Teil der Lösung
        letztes_element = i;   // aktualisieren
    end
end
return a  // menge ausgeben

ich hoffe mal, dass man mit dem code etwas weiterarbeiten kann

danke
mfG

 

[SlaterB]

siehe auch mein vorheriges Posting,
als Ergänzung vielleicht noch der wichtigste Tipp: die Überschneidung erstmal außen vor lassen, bzw. kannst du ja gerne auch programmieren,
das ist eine Sache,
das Finden der potentiellen Lösungen ist dazu quasi eine komplett andere,

erst die Möglichkeiten bestimmen, jede einzelne dann prüfen -> Lösung oder nicht

 

[joker123]

hm ja ok.
denke dann hab ich wirklich noch genug nachzuholen

trotzdem vielen dank für die Hilfe

 

[joker123]

hallo nochmal,

also ich wollte euch allen nochmal für die Hilfe danken, ich hab jetzt meinen Code soweit fertig, klappt nur noch nicht ganz.
aber das grundgerüst stimmt so, muss nur noch etwas an den Bedingungen arbeiten glaub ich

soll ich den code mal posten damit andere Benutzer sich mal inspirieren können falls sie mal ein ähnliches Problem haben ??

 

[SlaterB]

schadet nicht

 

[joker123]

package scheduling.intervalpartitioning;

import java.util.Iterator;
import java.util.Stack;

public class IntervalPartitioning
{
	public static int solve(int m , int[] s, int[] f)
	{
		int parts = m;
		
		Stack<Integer> hs = new Stack<Integer>();
			
		final boolean[] in = new boolean[m];
		
		
		for(int j=0; j < m-1; j++)
		{
			if(!in[j])	 // falls das Intervall noch in keiner Partition ist	
			{   
				hs.add(j); //Intervall in die Partition einf¸gen
				System.out.println(j);
				for(int i=1; i < m-1; i++)
				{
				    // W¸rde jede anderes Intervall testen ob es noch in eine Partition hineinpasst
					if(isComp(s[i],f[i],hs,s, f) && !in[i])
					{
						hs.add(i);
						System.out.println("Test: "+i+" bestanden");
						in[i] = true; // Intervall ist jetzt in einer Partition drin und somit nicht mehr f¸r eine andere verf¸gbar
						parts--; // Anzahl partitionen herunterz‰hlen
						
						
					}
				}
				hs.clear();
				

			}
		}
		return parts;
	}
	public static boolean isComp(int s, int f,Stack<Integer> hs,int[] ints, int[] intf)
	{
		boolean ret = true;
		for (Iterator<Integer> i = hs.iterator(); i.hasNext();)
        {
			int t = i.next();
			// Testen ob der aktuelle Wert noch in die aktuelle Partition passt
			if(s<intf[t] || f>ints[t]) 
			{
				System.out.println(s+" < "+intf[t]+" oder "+ f+" > "+ints[t]+" => false;");
				ret = false;
				
			}
        }
		
		return ret;
		
		
	}
	public static void main(String [] args)
	{
		 final int m = 10;
	     final int[] s = { 9, 16, 17, 5, 3, 18, 14, 4, 14, 17 };
	     final int[] f = { 15, 25, 24, 12, 11, 19, 15, 8, 16, 24 };

        final int resultIntervalPartitioning = IntervalPartitioning.solve(m, s, f);
        System.out.println("resultat: "+resultIntervalPartitioning);
        
       
	}
}

klappt halt noch nicht ganz, bei den Zeilen 25-32 muss noch ein Fehler sein, da nie auf "true" umgeschaltet wird...vielleicht sieht jemand auf die schnelle den Fehler

 

[joker123]

bin wieder ein Stück weiter gekommen...jetzt sind nur noch 2 Testfälle die nicht klappen