=== 路径规划 ===
我们有一个有向无环图，权重在节点上。
需求：从一个起点开始，找到一条节点权重之和最大的最优路径。
输入: n个节点，m个路径，起点
输出: 最优路径的权重值之和
举例:
3个节点与权重: A=1, B=2, C=2
3条路径: A->B, B->C, A->C
起点: A
输出: 5 (最优路径是 A->B->C ， 权重之和是 1+2+2=5)
NodeModel.h
#import <Foundation/Foundation.h>
NS_ASSUME_NONNULL_BEGIN
@interface NodeModel : NSObject
@property (nonatomic, copy) NSString *node;
@property (nonatomic, assign) NSInteger index;
@property (nonatomic, assign) NSInteger value;
-(void)currentValueAndIndex:(NSString *)node;
@end
NS_ASSUME_NONNULL_END
NodeModel.m
#import "NodeModel.h"
@implementation NodeModel
-(void)currentValueAndIndex:(NSString *)node{
_node = node;
if ([_node isEqualToString:@"A"]) {
_value = 0;
}else if ([_node isEqualToString:@"B"]) {
_value = 10;
}else if ([_node isEqualToString:@"C"]) {
_value = 3;
}else if ([_node isEqualToString:@"D"]) {
_value = 4;
}else if ([_node isEqualToString:@"E"]) {
_value = 5;
}else if ([_node isEqualToString:@"F"]) {
_value = 20;
}else if ([_node isEqualToString:@"G"]) {
_value = 7;
}else if ([_node isEqualToString:@"H"]) {
_value = 80;
}else if ([_node isEqualToString:@"I"]) {
_value = 9;
}
if ([_node isEqualToString:@"A"]) {
_index = 0;
}else if ([_node isEqualToString:@"B"]) {
_index = 1;
}else if ([_node isEqualToString:@"C"]) {
_index = 2;
}else if ([_node isEqualToString:@"D"]) {
_index = 3;
}else if ([_node isEqualToString:@"E"]) {
_index = 4;
}else if ([_node isEqualToString:@"F"]) {
_index = 5;
}else if ([_node isEqualToString:@"G"]) {
_index = 6;
}else if ([_node isEqualToString:@"H"]) {
_index = 7;
}else if ([_node isEqualToString:@"I"]) {
_index = 8;
}
}
@end
viewController中：
-(void)routePlanning{
NSMutableArray *nodeArray = [@[@"A", @"B", @"D", @"D", @"C", @"F", @"F", @"H", @"A"]copy];
NSMutableArray *array = [NSMutableArray array];
NSMutableDictionary *allDic = [NSMutableDictionary dictionary];
for (int i = 0; i<nodeArray.count; i++) {
NodeModel *model = [[NodeModel alloc]init];
model.node = [nodeArray objectAtIndex:i];
[model currentValueAndIndex:model.node];
[array addObject:model];
}
[array sortUsingComparator:^NSComparisonResult(NodeModel *obj1, NodeModel *obj2) {
return obj1.index > obj2.index;
}];
[self search:array allDic:allDic];
NSNumber *max = [allDic.allKeys valueForKeyPath:@"@max.floatValue"];
NSLog(@"%@",max);
NSArray *resultArray = [allDic valueForKey:[NSString stringWithFormat:@"%@",max]];
[resultArray enumerateObjectsUsingBlock:^(NodeModel *obj, NSUInteger idx, BOOL * _Nonnull stop) {
NSLog(@"%@ %ld %ld",obj.node,obj.index,obj.value);
}];
}
-(void)search:(NSMutableArray *)array allDic:(NSMutableDictionary *)allDic{
for (int i = 0; i<array.count; i++) {
NSMutableArray *sortArray = [NSMutableArray array];
/** 存储搜索后的model集合 */
NodeModel *lastModel = [array objectAtIndex:i];
NSMutableArray *nextArray = [[NSMutableArray arrayWithArray:array]mutableCopy];
[nextArray removeObject:lastModel];
/** 去重，减少循环次数 */
if (sortArray.count) {
NSMutableSet *nextSet = [NSMutableSet setWithArray:nextArray];
NSMutableSet *sortSet = [NSMutableSet setWithArray:sortArray];
[nextSet minusSet:sortSet];
nextArray = [nextSet.allObjects mutableCopy];
}
NodeModel *finalModel;
NodeModel *currentModel;
for (int j = 0; j<nextArray.count; j++) {
currentModel = [nextArray objectAtIndex:j];
if (!(currentModel.value > lastModel.value && currentModel.index > lastModel.index)) {
continue;
}
if (sortArray.count == 0) {
[sortArray addObject:lastModel];
finalModel = currentModel;
[sortArray addObject:finalModel];
}
/** 判断是否在左侧与右侧的范围 */
BOOL isLeftRange =
currentModel.value >= lastModel.value &&
currentModel.index >= lastModel.index &&
currentModel.value <= finalModel.value &&
currentModel.index <= finalModel.index;
/** 判断是否大于最右侧的范围 */
BOOL isRightRange =
currentModel.value > finalModel.value &&
currentModel.index > finalModel.index;
if (isRightRange) {
if (![sortArray containsObject:finalModel]) {
[sortArray addObject:finalModel];
}
if (![sortArray containsObject:currentModel]) {
[sortArray addObject:currentModel];
}
lastModel = finalModel;
finalModel = currentModel;
continue;
}
if (isLeftRange) {
if (![sortArray containsObject:lastModel]) {
[sortArray addObject:lastModel];
}
if (![sortArray containsObject:currentModel]) {
[sortArray addObject:currentModel];
}
if (sortArray.count == 2) {
lastModel = sortArray.firstObject;
}else{
lastModel = currentModel;
}
continue;
}
}
__block NSInteger sum = 0;
[sortArray enumerateObjectsUsingBlock:^(NodeModel *obj, NSUInteger idx, BOOL * _Nonnull stop) {
sum = sum + obj.value;
}];
[allDic setValue:sortArray forKey:[NSString stringWithFormat:@"%ld",sum]];
}
}
