Řešení KSP úlohy 33-3-4 Obsazování území https://ksp.mff.cuni.cz/h/ulohy/33/zadani3.html#task-33-3-4
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

222 lines 11 KiB Raw Permalink Blame History

 `use db::{MemoryLayoutDB, SqliteLayoutDB, LayoutDB, SavedLayout};` `use city::{City, House, HouseLayout, get_price};` `use itertools::Itertools;` `use rand::{thread_rng, Rng, SeedableRng};` `use rand::rngs::StdRng;` `use rayon::prelude::*;` `mod city;` `mod db;` `mod combine;` `mod subcity;` `mod optimization;` `mod population;` `fn main() {` ` let mut sqlite_db = SqliteLayoutDB::from_file("layouts.sqlite", false).expect("Failed to load the DB");` ` eprintln!("Loaded the DB, {} stored layouts", sqlite_db.layouts().len());` ` let city = City::read_from_file("01.in", city::INPUT_CITY_WIDTH, city::INPUT_CITY_HEIGHT);` ` eprintln!("Loaded the city file, {} houses", city.get_house_count());` ` let best_layout: SavedLayout = sqlite_db.layouts().iter()` ` .sorted_by(|x, y| get_price(&city, x.houses()).cmp(&get_price(&city, y.houses())))` ` .map(|layout| (*layout).clone())` ` .next().expect("No best layout found");` ` eprintln!("Found best layout, ID {}, price {}", best_layout.id(), get_price(&city, best_layout.houses()));` ` //let x_range = 5533..=12000;` ` //let y_range = 4750..=12500;` ` //let x_range = 9500..=14100;` ` //let y_range = 10300..=14400;` ` //let x_range = 14900..=16200;` ` //let y_range = 7720..=10400;` ` //let x_range = 9982..=16383;` ` //let y_range = 0..=2720;` ` //let x_range = 7720..=12000;` ` //let y_range = 5608..=11000;` ` //let x_range = 3542..=8423;` ` //let y_range = 4832..=8423;` ` //let x_range = 1200..=9200;` ` //let y_range = 9000..=16383;` ` //let x_range = 9200..=16383;` ` //let y_range = 9200..=16383;` ` //let x_range = 9201..=16383;` ` //let y_range = 0..=7500;` ` //let x_range = 11100..=13333;` ` //let y_range = 14700..=16383;` ` //let x_range = 0..=7500;` ` //let y_range = 0..=7500;` ` let x_range = 0..=7500;` ` let y_range = 9500..=16383;` ` //let x_range = 9500..=16383;` ` //let y_range = 0..=7500;` ` eprintln!("X {}-{}, Y {}-{}", x_range.start(), x_range.end(), y_range.start(), y_range.end());` ` let static_houses: Vec = best_layout.houses().iter()` ` .filter(|house| !(x_range.contains(&house.x) && y_range.contains(&house.y)))` ` .map(|&house| house)` ` .collect();` ` let removed_houses: Vec = best_layout.houses().iter()` ` .filter(|house| x_range.contains(&house.x) && y_range.contains(&house.y))` ` .map(|&house| house)` ` .collect();` ` let removed_price: u32 = removed_houses.iter().map(|x| city.get_price(*x) as u32).sum();` ` eprintln!("Price of all removed houses: {}", removed_price);` ` let subcity = subcity::build_subcity(&city, &static_houses);` ` eprintln!("Built subcity, width {}, height {}, {} houses, offset ({},{})",` ` subcity.city().width(),` ` subcity.city().height(),` ` subcity.city().get_house_count(),` ` subcity.x_offset(),` ` subcity.y_offset()` ` );` ` //let mut subcity_db = MemoryLayoutDB::new();` ` let filename = format!("X{}_{}Y{}_{}ID{}.sqlite", x_range.start(), x_range.end(), y_range.start(), y_range.end(), best_layout.id());` ` let mut subcity_db = SqliteLayoutDB::from_file(&filename, true).unwrap();` ` // The following part merges best subcity layouts back into the global layout and` ` // inserting them into the database` ` // Setting this value allows attempts at improving suboptimal subcities after merging them back.` ` // A subcity may result in a better score than original even if the subcity is worse than the` ` // original if global improvements improve the cost.` ` //const SUBOPTIMAL_SUBCITY_COST_MARGIN: u32 = 5000;` ` //const CHECKED_CITY_LIMIT: usize = 50;` ` //for layout in subcity_db.layouts().iter()` ` // .filter(|x| get_price(subcity.city(), x.houses()) < removed_price + SUBOPTIMAL_SUBCITY_COST_MARGIN)` ` // .sorted_by(|x, y| get_price(subcity.city(), x.houses()).cmp(&get_price(subcity.city(), y.houses())))` ` // .take(CHECKED_CITY_LIMIT) {` ` // let price = get_price(subcity.city(), layout.houses());` ` // let mut full_houses = subcity.to_full_houses(layout.houses());` ` // assert!(city::is_valid(&city, &full_houses).is_some());` ` // let mut house_layout = HouseLayout::new(&city);` ` // for house in &full_houses {` ` // house_layout.add_house(*house);` ` // }` ` // let seed: u64 = thread_rng().gen();` ` // let mut rng = StdRng::seed_from_u64(seed);` ` // optimization::iterate_improvements(&mut house_layout, &mut rng, true, false);` ` // eprintln!("Improvements finished");` ` // assert!(house_layout.is_valid());` ` // let improved_price = city::get_price(&city, house_layout.houses());` ` // if improved_price < city::get_price(&city, &full_houses) {` ` // eprintln!("Found improvement, new price {}, updating houses", improved_price);` ` // full_houses = house_layout.houses().clone();` ` // }` ` // assert!(city::is_valid(&city, &full_houses).is_some());` ` // println!("Layout {}, price {}, full price {}", layout.id(), price, city::get_price(&city, &full_houses));` ` // if improved_price < city::get_price(&city, best_layout.houses()) {` ` // eprintln!("Found a new best layout for the full city");` ` // println!("Found a new best layout for the full city");` ` // println!("Layout {}, price {}, full price {}", layout.id(), price, city::get_price(&city, &full_houses));` ` // }` ` // //eprintln!("NOT inserting into the DB");` ` // // Be careful with duplicates here` ` // sqlite_db.add_layout(&full_houses, true);` ` // eprintln!("Inserted into the global DB");` ` // println!("Inserted into the global DB");` ` // //}` ` //}` ` //return;` ` // Architecture:` ` // Build `FULL_RANDOM_LAYOUTS` random layouts` ` // loop {` ` // Try combining `CUT_COMBINE_TOP_LAYOUTS` top layouts using vertical/horizontal cuts` ` // Generate `WEIGHTED_RANDOM_LAYOUTS` layouts weighted by scores from existing layouts` ` // }` ` const FULL_RANDOM_LAYOUTS: usize = 200;` ` const DB_CHOICE_PROBABILITY: f64 = 0.95;` ` const WEIGHTED_RANDOM_LAYOUTS: usize = 100;` ` const CUT_COMBINE_TOP_LAYOUTS: usize = 500;` ` const IGNORED_WEIGHT_RATIO: f64 = 0.5;` ` const THREAD_COUNT: usize = 12;` ` rayon::ThreadPoolBuilder::new().num_threads(THREAD_COUNT).build_global();` ` if subcity_db.layouts().len() == 0 {` ` let mut full_random_layouts = Vec::new();` ` full_random_layouts.par_extend((0..FULL_RANDOM_LAYOUTS).into_par_iter().map(|i| {` ` let seed: u64 = thread_rng().gen();` ` let mut rng = StdRng::seed_from_u64(seed);` ` let mut layout = HouseLayout::new(subcity.city());` ` //eprintln!("Starting random population {}", i);` ` population::populate_random(&mut layout, &mut rng);` ` //eprintln!("Finished random init {}, price: {}, houses: {}", i, layout.price(), layout.houses().len());` ` optimization::iterate_improvements(&mut layout, &mut rng, false, false);` ` //eprintln!("Finished iterated improvements {}, price: {}, houses: {}", i, layout.price(), layout.houses().len());` ` layout.houses().clone()` ` }));` ` for houses in &full_random_layouts {` ` subcity_db.add_layout(houses, true).expect("Failed to add new layout");` ` }` ` eprintln!("Finished initial full random population");` ` } else {` ` eprintln!("Skipping initial full random population because DB is non-empty [{} layouts]", subcity_db.layouts().len());` ` }` ` fn print_status(db: &TDB, subcity: &City) {` ` let best_price: u32 = db.layouts().iter().map(|layout| layout.houses().iter().map(|h| subcity.get_price(*h) as u32).sum()).min().unwrap();` ` let worst_price: u32 = db.layouts().iter().map(|layout| layout.houses().iter().map(|h| subcity.get_price(*h) as u32).sum()).max().unwrap();` ` eprintln!("Best {}, worst {} [{} layouts]", best_price, worst_price, db.layouts().len());` ` }` ` print_status(&subcity_db, subcity.city());` ` let mut cache = combine::CompatibilityCache::new();` ` // TODO: Deduplication of the DB` ` loop {` ` // This is a bottleneck when it comes to multithreading, it only runs on a single thread` ` combine::iterate_combines(&mut subcity_db, CUT_COMBINE_TOP_LAYOUTS, subcity.city(), &mut cache, false);` ` eprintln!("Finished cut combines");` ` print_status(&subcity_db, subcity.city());` ` let mut weighted_random_layouts = Vec::new();` ` // Only using the underlying memory-based DB is required here as the SqliteLayoutDB` ` // is not thread-safe. We are only reading in the parallel iterator, so that's fine.` ` let memory_db = subcity_db.memory_db();` ` weighted_random_layouts.par_extend((0..WEIGHTED_RANDOM_LAYOUTS).into_par_iter().map(|i| {` ` let seed: u64 = thread_rng().gen();` ` let mut rng = StdRng::seed_from_u64(seed);` ` let mut layout = HouseLayout::new(subcity.city());` ` let best_price: u32 = memory_db.layouts().iter().map(|layout| layout.houses().iter().map(|h| subcity.city().get_price(*h) as u32).sum()).min().unwrap();` ` let worst_price: u32 = memory_db.layouts().iter().map(|layout| layout.houses().iter().map(|h| subcity.city().get_price(*h) as u32).sum()).max().unwrap();` ` let price_range = worst_price - best_price;` ` let max_price = best_price as f64 + (price_range as f64 * (1. - IGNORED_WEIGHT_RATIO));` ` //eprintln!("Starting random weighted population {}, using DB, score range {}-{}, DB use probability {}...", i, best_price, worst_price, DB_CHOICE_PROBABILITY);` ` population::populate_using_db(&mut layout, &mut rng, memory_db, best_price as f64, max_price as f64, DB_CHOICE_PROBABILITY);` ` //eprintln!("Finished random init {}, price: {}, houses: {}", i, layout.price(), layout.houses().len());` ` optimization::iterate_improvements(&mut layout, &mut rng, false, false);` ` //eprintln!("Finished iterated improvements {}, price: {}, houses: {}", i, layout.price(), layout.houses().len());` ` layout.houses().clone()` ` }));` ` for houses in &weighted_random_layouts {` ` subcity_db.add_layout(houses, true).expect("Failed to add new layout");` ` }` ` let w_best: u32 = weighted_random_layouts.iter().map(|houses| houses.iter().map(|h| subcity.city().get_price(*h) as u32).sum()).min().unwrap();` ` let w_worst: u32 = weighted_random_layouts.iter().map(|houses| houses.iter().map(|h| subcity.city().get_price(*h) as u32).sum()).max().unwrap();` ` eprintln!("Finished weighted random population, price range {}-{}", w_best, w_worst);` ` print_status(&subcity_db, subcity.city());` ` }` ```} ``` ``` ```